Big-O cheat sheet
BytePatterns'teki her veri yapısı ve algoritmanın zaman ve alan karmaşıklığı, hash tablolarından Dijkstra'ya; her satır animasyonlu dersine bağlı.
Güncellendi: 78 satır94 ders bağlantısıTemiz yazdırılır; tarayıcının yazdırma özelliğini kullan
Nasıl okunur
- n girdi boyutudur. Sabitler ve küçük terimler atılır: 3n + 5, O(n)'dir.
- Hücrede avg ya da amortized yazmıyorsa zaman en kötü durumdur (amortize: biri pahalı olsa bile uzun bir işlem dizisinde ortalamada ucuz).
- Alan, ek alandır: girdinin üstüne harcanan bellek, çıktı sayılmaz. Özyineleme sayılır: call stack'i de alandır.
- V ve E düğümler ve kenarlardır; m ve n, iki string'li ya da grid problemindeki iki uzunluktur. Diğer her harf kendi satırında tanımlanır.
- Sabit ya da logaritmik
- Doğrusal ya da n log n
- Polinom
- Üstel ya da faktöriyel
Gösterime yeni misin? Big-O modülü onu her seferinde tek bir fikirle anlatır: Big-O nedir?, O(1) ve O(n), O(log n) ve yarıya bölme, O(n²) ve iç içe döngüler, Karmaşıklıkları karşılaştırmak.
Büyüme dereceleri
Sayılardan çok şekil önemli: n = 100'de sorun çıkarmayan bir O(n²) çözüm n = 100.000'de umutsuzdur. Grafik küçük n için şekli gösterir; tablo gerçek kısıtlarda karşına çıkan boyutlardaki adım sayılarını gösterir.
| Derece | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| O(1) sabit | 1 | 1 | 1 |
| O(log n) logaritmik | 3.3 | 10 | 19.9 |
| O(n) doğrusal | 10 | 1,000 | 1,000,000 |
| O(n log n) doğrusal-logaritmik | 33.2 | 9,966 | ≈ 107 |
| O(n2) karesel | 100 | 1,000,000 | ≈ 1012 |
| O(2n) üstel | 1,024 | ≈ 10301 | ≈ 10301029 |
| O(n!) faktöriyel | 3,628,800 | ≈ 102567 | ≈ 105565708 |
| Girdi sınırı | Genellikle sığan |
|---|---|
| n ≤ 10 | O(n!) |
| n ≤ 20 | O(2n) |
| n ≤ 500 | O(n3) |
| n ≤ 5.000 | O(n2) |
| n ≤ 106 | O(n log n) |
| n ≤ 107 | O(n) |
| daha büyük | O(log n) ya da O(1) |
Bir saniyelik sınır için pratik bir kural; saniyede kabaca 10⁷–10⁸ basit adım varsayar. Sabit çarpanlar ve dil bunu kaydırır; satırların sırası değişmez.
Veri yapıları
Her işlemin maliyeti. Kart başlıkları onu canlandıran derse bağlanır.
Dizi (dinamik)
- İndeksle okuma / yazma
- O(1)
- Arama (sırasız)
- O(n)
- Sona ekleme
- O(1) amortized
- Ortaya ekleme / ortadan silme
- O(n)
- Alan
- O(n)
Boşluktan sonraki her eleman kaydırılmak zorunda.
Tek yönlü bağlı liste
- k'ıncı düğüme ulaşma
- O(n)
- Arama
- O(n)
- Başa ekleme / baştan silme
- O(1)
- Bilinen bir düğümden sonra ekleme / silme
- O(1)
- Alan
- O(n)
Ayrıca bak: Ekleme ve silme
Çift yönlü bağlı liste
- İki uçta da push / pop
- O(1)
- Elindeki bir düğümü listeden çıkarma
- O(1)
- Arama
- O(n)
- Alan
- O(n)
Düğümü çıkarmayı O(1) yapan, prev pointer'ı (işaretçi); bir LRU cache'in özü de bu.
Stack
- Push / pop / peek
- O(1)
- Arama
- O(n)
- Alan
- O(n)
Kuyruk / deque
- Kuyruğa ekleme / kuyruktan çıkarma
- O(1)
- Baştakine bakma
- O(1)
- Arama
- O(n)
- Alan
- O(n)
Düz bir dizinin başından silmek O(n)'dir; deque ya da ring buffer kullan.
Ayrıca bak: Dairesel kuyruk
Hash tablosu (map / set)
- Arama
- O(1) avgO(n) worst
- Ekleme
- O(1) avgO(n) worst
- Silme
- O(1) avgO(n) worst
- Alan
- O(n)
En kötü durum, her anahtarın tek bir bucket'a düşmesidir. Sıra yoktur: sıralı dolaşmak O(n log n) tutar.
Ayrıca bak: Hashing ne zaman başarısız olur?
İkili heap
- Min / max'a bakma
- O(1)
- Push
- O(log n)
- Min / max'ı pop etme
- O(log n)
- n öğeden kurma (heapify)
- O(n)
- Arama
- O(n)
- Alan
- O(n)
Ayrıca bak: Heapify ve sift · Öncelik kuyruğu
İkili arama ağacı
- Arama / ekleme / silme
- O(h)
- …dengeliyse
- O(log n)
- …dejenere olmuşsa (zincir)
- O(n)
- Inorder dolaşma
- O(n)
- Alan
- O(n)
h yüksekliktir. Sıralı girdi o zinciri kurar.
Ayrıca bak: BST'de ekleme ve arama · Ağaç derinliği ve denge
Trie
- Kelime ekleme
- O(L)
- Kelime arama
- O(L)
- Bir prefix'le başlayan var mı
- O(L)
- Alan
- O(total characters)
L, kelimenin ya da prefix'in (önek) uzunluğudur; kaç kelime saklandığından bağımsızdır.
Ayrıca bak: Prefix arama · Trie mi, hash set mi
Union-find (disjoint set)
- Find / union, iki optimizasyonla
- O(α(n)) amortized
- …yalnız union by size ile
- O(log n)
- …ikisi de yoksa
- O(n)
- Alan
- O(n)
α, ters Ackermann fonksiyonudur: belleğe sığan her girdi için en fazla 4.
Ayrıca bak: Path compression · Union by rank ya da size
Graf — komşuluk listesi
- u → v kenarı var mı?
- O(deg u)
- u'nun tüm komşularını dolaşma
- O(deg u)
- Kenar ekleme
- O(1)
- Alan
- O(V + E)
Seyrek graflar için varsayılan seçim; mülakat graflarının çoğu da seyrektir.
Ayrıca bak: Graf temelleri
Graf — komşuluk matrisi
- u → v kenarı var mı?
- O(1)
- u'nun tüm komşularını dolaşma
- O(V)
- Kenar ekleme
- O(1)
- Alan
- O(V2)
Yalnız graf yoğunsa ya da V küçükse değer.
Sıralama
Karşılaştırma tabanlı sıralamalar en kötü durumda O(n log n)'i geçemez; counting sort ve radix sort karşılaştırma yapmadan bu sınırın etrafından dolaşır.
| Algoritma | En iyi | Ortalama | En kötü | Alan | Kararlı | Notlar |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n2) | O(n2) | O(1) | Evet | O(n) en iyi durum için, hiç yer değiştirme olmayınca duran kontrol şart. |
| Selection sort | O(n2) | O(n2) | O(n2) | O(1) | Hayır | En fazla n − 1 yer değiştirme; tek artısı bu. |
| Insertion sort | O(n) | O(n2) | O(n2) | O(1) | Evet | Neredeyse sıralı girdide hızlı. |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Evet | |
| Quicksort | O(n log n) | O(n log n) | O(n2) | O(log n) | Hayır | En kötü durum art arda kötü pivotlardan gelir; stack o zaman O(n)'e büyü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 | k, değer aralığıdır. Yalnız tam sayılar (ya da anahtarlar) için. |
| Radix sort | O(d·(n + b)) | O(d·(n + b)) | O(d·(n + b)) | O(n + b) | Evet | b tabanında d basamak; basamak başına bir kararlı geçiş. |
Arama
| Algoritma | Zaman | Alan | Notlar |
|---|---|---|---|
| Doğrusal arama | O(n) | O(1) | |
| İkili arama | O(log n) | O(1) | Sıralı girdi. İteratif; özyinelemeli sürüm O(log n) stack ekler. |
| Döndürülmüş sıralı dizide arama | O(log n) | O(1) | Değerler birbirinden farklı. Tekrar eden değerler O(n)'e zorlayabilir. |
| Tepe noktası bulma | O(log n) | O(1) | |
| Cevap üzerinde ikili arama | O(Clog R) | O(1) | R cevap aralığının boyutu, C tek bir uygunluk kontrolünün maliyeti. |
| Sıralı 2D matriste arama (merdiven) | O(m + n) | O(1) | m satır, n sütun; her adım bir satırı ya da bir sütunu eler. |
Dizi, liste ve string teknikleri
| Algoritma | Zaman | Alan | Notlar |
|---|---|---|---|
| İki pointer | O(n) | O(1) | |
| Kayan pencere | O(n) | O(k) | Her eleman bir kez girer, bir kez çıkar; k, pencerenin hatırlaması gereken şeydir. |
| Prefix sum | O(n) buildO(1) per query | O(n) | |
| Hash map ile subarray toplamı | O(n) | O(n) | |
| Kadane ile maksimum subarray | O(n) | O(1) | |
| Kendisi hariç çarpım | O(n) | O(1) | Çıktı dizisi sayılmadan. |
| Dutch National Flag (üçlü bölümleme) | O(n) | O(1) | |
| Hızlı ve yavaş pointer (döngü tespiti) | O(n) | O(1) | |
| Bağlı listeyi ters çevirme | O(n) | O(1) | İteratif. Özyineleme O(n) stack harcar. |
| Monoton stack | O(n) amortized | O(n) | Her eleman bir kez push, en fazla bir kez pop edilir. |
| Kayan pencere maksimumu (deque) | O(n) | O(k) | |
| KMP ile string eşleştirme | O(n + m) | O(m) | n metnin, m aranan kalıbın uzunluğu. |
| Rabin–Karp rolling hash | O(n + m) avgO(n·m) worst | O(1) | En kötü durum, her pencerenin hash'i çakıştığında. |
| Z algoritması | O(n + m) | O(n + m) |
Heap'ler ve sıralama
| Algoritma | Zaman | Alan | Notlar |
|---|---|---|---|
| k boyutlu heap ile top-k | O(n log k) | O(k) | |
| Bucket'larla en sık top-k | O(n) | O(n) | |
| K-way merge | O(N log k) | O(k) | k sıralı listede toplam N öğe. |
| Anlık medyan (iki heap) | O(log n) addO(1) median | O(n) | |
| Aralıkları birleştirme | O(n log n) | O(n) | Maliyeti sıralama belirler; tarama O(n). |
| Meeting Rooms (bitiş zamanlarının min-heap'i) | O(n log n) | O(n) |
Graflar ve grid'ler
| Algoritma | Zaman | Alan | Notlar |
|---|---|---|---|
| Genişlik öncelikli arama | O(V + E) | O(V) | |
| Derinlik öncelikli arama | O(V + E) | O(V) | Özyinelemeli DFS uzun bir yolda stack sınırına takılabilir. |
| Ağırlıksız en kısa yol (BFS) | O(V + E) | O(V) | |
| Grid'de flood fill / adalar | O(R·C) | O(R·C) | R satır × C sütun: her hücre bir kez ziyaret edilir. |
| Topolojik sıralama (Kahn) | O(V + E) | O(V) | |
| Dijkstra (ikili heap) | O((V + E) log V) | O(V) | Yalnız negatif olmayan ağırlıklar. |
| Bellman–Ford | O(V·E) | O(V) | Negatif ağırlıklarla çalışır, negatif döngüleri de tespit eder. |
| Kruskal ile MST | O(E log E) | O(V) | Kenarları sırala, sonra union-find. |
| Prim ile MST (ikili heap) | O(E log V) | O(V) | |
| İki parçalı graf kontrolü (2 renklendirme) | O(V + E) | O(V) | |
| Güçlü bağlı bileşenler | O(V + E) | O(V) |
Dinamik programlama
| Algoritma | Zaman | Alan | Notlar |
|---|---|---|---|
| Climbing Stairs / Fibonacci tarzı | O(n) | O(1) | Tablo yerine güncellenen iki değişken. |
| House Robber | O(n) | O(1) | |
| Coin Change (en az bozuk para) | O(n·A) | O(A) | n para türü, A tutar. |
| 0/1 knapsack | O(n·W) | O(W) | W kapasitedir; tek satır, sağdan sola doldurulur. |
| En uzun ortak alt dizi | O(m·n) | O(m·n) | Yalnız uzunluk gerekiyorsa O(min(m, n)) alan. |
| Edit distance | O(m·n) | O(m·n) | |
| En uzun artan alt dizi (DP) | O(n2) | O(n) | |
| En uzun artan alt dizi (tails) | O(n log n) | O(n) | |
| Grid'de yollar | O(m·n) | O(n) | Tablonun her seferinde tek bir satırı. |
| Aralık DP'si (matris zinciri sırası) | O(n3) | O(n2) |
Özyineleme ve backtracking
| Algoritma | Zaman | Alan | Notlar |
|---|---|---|---|
| Naif özyinelemeli Fibonacci | O(2n) | O(n) | Bir üst sınır; sıkı sınır yaklaşık 1,618ⁿ. |
| Memoization'lı özyineleme (Fibonacci) | O(n) | O(n) | |
| Tüm alt kümeler | O(n·2n) | O(n) | Çıktı sayılmadan. |
| Tüm permütasyonlar | O(n·n!) | O(n) | Çıktı sayılmadan. |
| N-Queens | O(n!) | O(n) | Üst sınır; budama çoğunu keser. |
Matematik ve bitler
| Algoritma | Zaman | Alan | Notlar |
|---|---|---|---|
| EBOB (Öklid) | O(log min(a, b)) | O(1) | |
| Hızlı üs alma | O(log n) | O(1) | İteratif kare alma; n üstür. |
| Eratosthenes kalburu | O(n log log n) | O(n) | |
| XOR ile tek kalan sayıyı bulma | O(n) | O(1) | |
| 1 olan bitleri sayma (en düşük 1'i silerek) | O(k) | O(1) | k, 1 olan bit sayısıdır; en fazla word boyutu kadar. |
| İkinin kuvveti kontrolü | O(1) | O(1) |
bytepatterns.com/cheatsheets/big-o — oradaki her satır animasyonlu bir derse bağlı.