Temel veri yapılarında yaygın işlemlerin Big-O karmaşıklıkları nelerdir?
Cevap
Big-O, girdi büyüdükçe çalışma süresinin veya bellek kullanımının en kötü durumda nasıl büyüdüğünü ifade eder. Sabitler ve küçük terimler atılır: 3n + 5 -> O(n).
| Yapı | Erişim | Arama | Ekleme | Silme |
|---|---|---|---|---|
| Dizi (array) | O(1) | O(n) | Sona O(1) amortize, araya O(n) | O(n) |
| Bağlı liste | O(n) | O(n) | Başa O(1) | Düğüm biliniyorsa O(1) |
| Hash table | - | O(1) ort., O(n) en kötü | O(1) ort. | O(1) ort. |
| Dengeli BST | O(log n) | O(log n) | O(log n) | O(log n) |
| Binary heap | Min/max O(1) | O(n) | O(log n) | Kök O(log n) |
| Stack / Queue | Uç O(1) | O(n) | O(1) | O(1) |
Büyüme sırası
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
- Karşılaştırmaya dayalı sıralama en iyi
O(n log n)olabilir. - İç içe iki döngü genelde
O(n²). - Her adımda problemi yarıya indirmek
O(log n).
def has_duplicate(nums): # O(n) zaman, O(n) bellek
seen = set()
for x in nums:
if x in seen: # set araması ortalama O(1)
return True
seen.add(x)
return FalseAynı problem iç içe döngüyle O(n²) zaman ama O(1) bellekle çözülür; mülakatta bu zaman-bellek takasını açıkça söylemek beklenir.
İlgili Algoritmalar & Veri Yapıları soruları
- Binary search'ün zaman karmaşıklığı nedir ve neden?
- Two Sum: toplamı hedefe eşit olan iki elemanın indekslerini bulun.
- Bir parantez dizisinin geçerli olup olmadığını kontrol edin: "({[]})"
- Tek yönlü bağlı listeyi ters çevirin.
- BFS ve DFS arasındaki fark nedir? Hangisini ne zaman kullanırsınız?
- get ve put işlemleri O(1) olan bir LRU Cache tasarlayın.
Bu konuda başka bir soru biliyor musun?
Mülakatta karşılaştığın soruları ekle, onaylandıktan sonra yayına alınsın.