İçeriğe geç

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.

Yaygın karmaşıklık sınıfları nasıl büyür1'den 20'ye girdi boyutu n'ye karşı adım sayısı, 60 adımda kesilmiş. O(1) düz kalır, O(log n) zar zor yükselir; O(n) düzenli tırmanır, O(n log n) biraz daha hızlı; O(n²) n 8'e varmadan, O(2ⁿ) 6'ya ve O(n!) 5'e varmadan grafikten çıkar.15101520girdi boyutu n →adım →O(n!)O(2n)O(n2)O(n log n)O(1)O(log n)O(n)
n = 1'den 20'ye n'ye karşı adım sayısı, 60 adımda kesilmiş.
Gerçek girdi boyutlarında adım sayısı
Derecen = 10n = 1,000n = 1,000,000
O(1) sabit111
O(log n) logaritmik3.31019.9
O(n) doğrusal101,0001,000,000
O(n log n) doğrusal-logaritmik33.29,966≈ 107
O(n2) karesel1001,000,000≈ 1012
O(2n) üstel1,024≈ 10301≈ 10301029
O(n!) faktöriyel3,628,800≈ 102567≈ 105565708
Kısıttan karmaşıklığa
Girdi sınırıGenellikle sığan
n ≤ 10O(n!)
n ≤ 20O(2n)
n ≤ 500O(n3)
n ≤ 5.000O(n2)
n ≤ 106O(n log n)
n ≤ 107O(n)
daha büyükO(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.

Sıralama algoritmaları: en iyi, ortalama ve en kötü zaman, ek alan ve kararlılık
AlgoritmaEn iyiOrtalamaEn kötüAlanKararlıNotlar
Bubble sortO(n)O(n2)O(n2)O(1)EvetO(n) en iyi durum için, hiç yer değiştirme olmayınca duran kontrol şart.
Selection sortO(n2)O(n2)O(n2)O(1)HayırEn fazla n − 1 yer değiştirme; tek artısı bu.
Insertion sortO(n)O(n2)O(n2)O(1)EvetNeredeyse sıralı girdide hızlı.
Merge sortO(n log n)O(n log n)O(n log n)O(n)Evet
QuicksortO(n log n)O(n log n)O(n2)O(log n)HayırEn kötü durum art arda kötü pivotlardan gelir; stack o zaman O(n)'e büyür.
Heap sortO(n log n)O(n log n)O(n log n)O(1)Hayır
Counting sortO(n + k)O(n + k)O(n + k)O(n + k)Evetk, değer aralığıdır. Yalnız tam sayılar (ya da anahtarlar) için.
Radix sortO(d·(n + b))O(d·(n + b))O(d·(n + b))O(n + b)Evetb tabanında d basamak; basamak başına bir kararlı geçiş.

Arama

Arama: zaman ve ek alan
AlgoritmaZamanAlanNotlar
Döndürülmüş sıralı dizide aramaO(log n)O(1)Değerler birbirinden farklı. Tekrar eden değerler O(n)'e zorlayabilir.
Tepe noktası bulmaO(log n)O(1)
Cevap üzerinde ikili aramaO(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

Dizi, liste ve string teknikleri: zaman ve ek alan
AlgoritmaZamanAlanNotlar
İki pointerO(n)O(1)
Kayan pencereO(n)O(k)Her eleman bir kez girer, bir kez çıkar; k, pencerenin hatırlaması gereken şeydir.
Prefix sumO(n) buildO(1) per queryO(n)
Hash map ile subarray toplamıO(n)O(n)
Kadane ile maksimum subarrayO(n)O(1)
Kendisi hariç çarpımO(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 çevirmeO(n)O(1)İteratif. Özyineleme O(n) stack harcar.
Monoton stackO(n) amortizedO(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ştirmeO(n + m)O(m)n metnin, m aranan kalıbın uzunluğu.
Rabin–Karp rolling hashO(n + m) avgO(n·m) worstO(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

Heap'ler ve sıralama: zaman ve ek alan
AlgoritmaZamanAlanNotlar
k boyutlu heap ile top-kO(n log k)O(k)
Bucket'larla en sık top-kO(n)O(n)
K-way mergeO(N log k)O(k)k sıralı listede toplam N öğe.
Anlık medyan (iki heap)O(log n) addO(1) medianO(n)
Aralıkları birleştirmeO(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

Graflar ve grid'ler: zaman ve ek alan
AlgoritmaZamanAlanNotlar
Ağırlıksız en kısa yol (BFS)O(V + E)O(V)
Grid'de flood fill / adalarO(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–FordO(V·E)O(V)Negatif ağırlıklarla çalışır, negatif döngüleri de tespit eder.
Kruskal ile MSTO(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şenlerO(V + E)O(V)

Dinamik programlama

Dinamik programlama: zaman ve ek alan
AlgoritmaZamanAlanNotlar
Climbing Stairs / Fibonacci tarzıO(n)O(1)Tablo yerine güncellenen iki değişken.
House RobberO(n)O(1)
Coin Change (en az bozuk para)O(n·A)O(A)n para türü, A tutar.
0/1 knapsackO(n·W)O(W)W kapasitedir; tek satır, sağdan sola doldurulur.
En uzun ortak alt diziO(m·n)O(m·n)Yalnız uzunluk gerekiyorsa O(min(m, n)) alan.
Edit distanceO(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 yollarO(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

Özyineleme ve backtracking: zaman ve ek alan
AlgoritmaZamanAlanNotlar
Naif özyinelemeli FibonacciO(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ümelerO(n·2n)O(n)Çıktı sayılmadan.
Tüm permütasyonlarO(n·n!)O(n)Çıktı sayılmadan.
N-QueensO(n!)O(n)Üst sınır; budama çoğunu keser.

Matematik ve bitler

Matematik ve bitler: zaman ve ek alan
AlgoritmaZamanAlanNotlar
EBOB (Öklid)O(log min(a, b))O(1)
Hızlı üs almaO(log n)O(1)İteratif kare alma; n üstür.
Eratosthenes kalburuO(n log log n)O(n)
XOR ile tek kalan sayıyı bulmaO(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ı.