Algoritma Analizi dersinde işlenen temel algoritmaların Python implementasyonları, kapsamlı açıklamaları ve karmaşıklık analizleri.
| Dosya | Algoritma | Zaman Karmaşıklığı | Uzay Karmaşıklığı |
|---|---|---|---|
01_bubble_sort.py |
Bubble Sort | O(n²) | O(1) |
02_selection_sort.py |
Selection Sort | O(n²) | O(1) |
03_insertion_sort.py |
Insertion Sort | O(n) – O(n²) | O(1) |
04_merge_sort.py |
Merge Sort | O(n log n) | O(n) |
05_quick_sort.py |
Quick Sort | O(n log n) – O(n²) | O(log n) |
06_binary_search.py |
Binary Search | O(log n) | O(1) |
07_max_subarray.py |
Max Subarray (Kadane's + D&C) | O(n) / O(n log n) | O(1) |
08_power_exponentiation.py |
Üssü Alma (Binary Exponentiation) | O(log n) | O(1) |
09_heap_sort.py |
Heap Sort | O(n log n) | O(1) |
10_counting_and_radix_sort.py |
Counting Sort & Radix Sort | O(n+k) / O(d·n) | O(n+k) |
11_dynamic_programming.py |
Dinamik Programlama (Fib, LCS, Knapsack) | Değişken | Değişken |
12_graph_bfs_dfs.py |
BFS & DFS | O(V+E) | O(V) |
| Algoritma | En İyi | Ortalama | En Kötü | Uzay | Kararlı? |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Evet |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ Hayır |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ Evet |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ Evet |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ Hayır |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ Hayır |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(n+k) | ✅ Evet |
| Radix Sort | O(d·n) | O(d·n) | O(d·n) | O(n+k) | ✅ Evet |
Algorithm-Analysis/
│
├── 01_bubble_sort.py ← Karşılaştırma: O(n²), Yerinde, Kararlı
├── 02_selection_sort.py ← Her durumda O(n²), az takas yapar
├── 03_insertion_sort.py ← Online, Adaptif, Küçük n için ideal
├── 04_merge_sort.py ← Böl & Fethet, garantili O(n log n)
├── 05_quick_sort.py ← Pratikte en hızlı, O(n²) riski var
├── 06_binary_search.py ← O(log n) arama, sıralı dizi gerekir
├── 07_max_subarray.py ← Kadane O(n), D&C O(n log n)
├── 08_power_exponentiation.py ← Fast Power O(log n), Modüler üs
├── 09_heap_sort.py ← Max-Heap, O(n log n), O(1) uzay
├── 10_counting_and_radix_sort.py ← Karşılaştırmasız, O(n+k)
├── 11_dynamic_programming.py ← Fib, LCS, 0/1 Knapsack
├── 12_graph_bfs_dfs.py ← BFS, DFS, Topo-sıra, Bağlı bileşen
└── README.md ← Bu dosya
Algoritmanın en kötü durumda performansını ifade eder.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
Sabit Logaritmik Lineer Lineer-log Kare Üstel Faktöriyel
| Algoritma | Recurrence | Sonuç |
|---|---|---|
| Binary Search | T(n) = T(n/2) + O(1) | O(log n) |
| Merge Sort | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Quick Sort (ort.) | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Max Subarray D&C | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Binary Exp. | T(n) = T(n/2) + O(1) | O(log n) |
# Top-Down (Memoization)
memo = {}
def dp(state):
if state in memo: return memo[state]
result = ... # alt problemleri çöz
memo[state] = result
return result
# Bottom-Up (Tabulation)
dp = [0] * (n + 1)
dp[0] = base_case
for i in range(1, n + 1):
dp[i] = f(dp[i-1], ...) # alt problem sonuçlarından üstHer Python dosyası bağımsız olarak çalıştırılabilir:
python 01_bubble_sort.py
python 04_merge_sort.py
python 11_dynamic_programming.py
# ... vb.Her script çalıştırıldığında:
- Örnek çıktılar görüntülenir
- Adım adım açıklamalar verilir
- Karmaşıklık özeti yazdırılır
| Durum | Önerilen Algoritma |
|---|---|
| Küçük diziler (n < 20) | Insertion Sort |
| Genel amaçlı | Quick Sort (Randomized) |
| Kararlılık gerekli | Merge Sort |
| Garanti O(n log n), O(1) uzay | Heap Sort |
| Küçük değer aralığı (tamsayı) | Counting Sort |
| Büyük tamsayılar (sabit basamak) | Radix Sort |
| Durum | Önerilen Algoritma |
|---|---|
| Sırasız dizi | Linear Search O(n) |
| Sıralı dizi | Binary Search O(log n) |
| Çizgede kısa yol (ağırlıksız) | BFS O(V+E) |
| Çizgede derin arama / topo sıra | DFS O(V+E) |
Her algoritma dosyası başında kapsamlı açıklama, karmaşıklık tablosu, görsel örnek ve test senaryoları içerir.