Big O Notasyonu ile Performans Değerlendirmesi
* List.append() amortize O(1)'dir: Çoğu zaman O(1), nadiren yeniden boyutlandırma gerektiğinde O(n). Ortalaması O(1) olarak kabul edilir.
O(n) - Sabit boyut
Bellek kullanımı öngörülebilir. Önceden ayrılmış alan.
O(n) - Değişken boyut
Yeniden boyutlandırma maliyeti. Hafıza parçalanması riski.
Zaman karmaşıklığını anlamak için veri yapılarının bellekte nasıl tutulduğunu bilmek gerekir.
Python listesi bellekte yan yana (contiguous) tutulur, tıpkı bir dizi kutu gibi:
Baştan eleman sildiğinizde, tüm elemanlar bir adres sola kaymak zorunda:
n-1 kaydırma işlemi = O(n)
Deque, elemanları pointer'larla birbirine bağlar. Bellekte yan yana olmak zorunda değiller:
Sadece HEAD pointer'ını güncelle, kaydırma yok:
Sadece 3 işlem = O(1) (eleman sayısından bağımsız!)
O(n)
n eleman = n kaydırma
O(1)
n eleman = 3 pointer işlemi
Farklı Queue implementasyonlarını test edelim ve O(n) vs O(1) farkını gözlemleyelim:
import time
from collections import deque
def benchmark_list_queue(n):
"""List ile Queue simülasyonu - O(n) dequeue"""
q = []
# Enqueue - O(1) amortized
start = time.time()
for i in range(n):
q.append(i)
enqueue_time = time.time() - start
# Dequeue - O(n) her seferinde!
start = time.time()
while q:
q.pop(0) # Bu O(n) çünkü kaydırma yapıyor
dequeue_time = time.time() - start
return enqueue_time, dequeue_time
def benchmark_deque(n):
"""Deque ile Queue - O(1) her işlem"""
q = deque()
# Enqueue - O(1)
start = time.time()
for i in range(n):
q.append(i)
enqueue_time = time.time() - start
# Dequeue - O(1)
start = time.time()
while q:
q.popleft() # Bu O(1) çünkü pointer güncellemesi
dequeue_time = time.time() - start
return enqueue_time, dequeue_time
# Farklı boyutlarda test
print("=" * 65)
print("🧪 QUEUE PERFORMANS BENCHMARKı")
print("=" * 65)
print(f"{'Eleman':>10} | {'List Dequeue':>15} | {'Deque Dequeue':>15} | {'Fark':>10}")
print("-" * 65)
for n in [1000, 5000, 10000]:
list_enq, list_deq = benchmark_list_queue(n)
deque_enq, deque_deq = benchmark_deque(n)
if deque_deq > 0:
fark = list_deq / deque_deq
else:
fark = float('inf')
print(f"{n:>10,} | {list_deq:>13.4f}s | {deque_deq:>13.4f}s | {fark:>8.1f}x")
print("-" * 65)
print("\n📊 SONUÇ ANALİZİ:")
print("=" * 65)
print("""
🔴 LIST (pop(0)):
- Her dequeue'da TÜM elemanlar kaydırılır
- 10,000 eleman = ~50 milyon kaydırma işlemi (n × n/2)
- Zaman karmaşıklığı: O(n) per operation → O(n²) toplam
🟢 DEQUE (popleft):
- Sadece pointer güncellenir
- 10,000 eleman = 10,000 pointer güncellemesi
- Zaman karmaşıklığı: O(1) per operation → O(n) toplam
💡 Büyük n'lerde fark KATLANARAK artar!
- n = 1000 → ~10x fark
- n = 10000 → ~100x fark
- n = 100000 → ~1000x fark (tahmin)
""")■ O(1) - Deque/Circular ■ O(n) - List pop(0)