Bilgisayar bilimlerinde zaman karmaşıklığı, bir algoritmayı çalıştırmak için gereken bilgisayar süresini tanımlayan hesaplama karmaşıklığıdır. Zaman karmaşıklığı genellikle, her bir temel işlemin gerçekleştirilmesinin sabit bir zaman aldığı varsayılarak, algoritma tarafından gerçekleştirilen temel işlemlerin sayısı sayılarak tahmin edilir. Bu fonksiyonun tam olarak hesaplanması genellikle zor olduğundan ve küçük girdiler için çalışma süresi genellikle önemli olmadığından, genellikle girdi boyutu arttığında karmaşıklığın davranışına, yani karmaşıklığın asimptotik davranışına odaklanılır.
Bu nedenle, zaman karmaşıklığı genellikle big O gösterimi kullanılarak ifade edilir, tipik olarak O(1), O(n), O(Log n) vb. gösterimler kullanılır. burada n, girdiyi temsil etmek için gereken bit birimi cinsinden boyuttur. Ancak big O gösteriminin hikayenin tamamı olmadığını unutmayın. Bunun için yazının son kısımlarına göz atmanızda fayda var!
Big O notasyonu‘nun teknik açıklaması ile başlayalım. Büyük O notasyonu veya zaman karmaşıklığı, argüman belirli bir değere veya sonsuza doğru yöneldiğinde bir fonksiyonun sınırlayıcı davranışını tanımlayan matematiksel bir gösterimdir. Büyük O, Paul Bachmann, Edmund Landa ve diğerleri tarafından uyarlanan ve topluca Bachmann-Landau notasyonu veya asimptotik notasyon olarak adlandırılan bir notasyon ailesinin üyesidir. O harfi Bachmann tarafından Ordnung, yani yaklaşım sırası anlamına gelmek üzere seçilmiştir.
Bilgisayar dillerinde big O gösterimi, algoritmaları girdi boyutu büyüdükçe çalışma sürelerinin veya alan gereksinimlerinin nasıl büyüdüğüne göre sınıflandırmak için kullanılır. Büyük O gösterimi diğer birçok alanda da benzer tahminler sağlamak için kullanılır.
Teknik bir girişten sonra basitçe zaman karmaşıklığının ne olduğuna bakalım:
Basitçe Big O Notasyonu
Big-O gösteriminin kodunuz için ifade ettiği en önemli şey, üzerinde çalıştığı “şeylerin” miktarını iki katına çıkardığınızda kodunuzun nasıl ölçekleneceğini göstermesidir. Somut bir örneğe bakalım:
Big-O | 10 şey için hesaplama | 100 şey için hesaplama ---------------------------------------------------------------------- O(1) | 1 | 1 O(log(n)) | 3 | 7 O(n) | 10 | 100 O(n log(n)) | 30 | 700 O(n^2) | 100 | 10000
O(n log(n)) olan quicksort ile O(n^2) olan bubble sort’ı ele alalım. 10 şeyi sıralarken, quicksort bubble sort’tan 3 kat daha hızlıdır. Ancak 100 şeyi sıralarken 14 kat daha hızlıdır! En hızlı algoritmayı seçmenin önemli olduğu açıksa; bu, milyon satırlı veritabanlarına ulaştığınızda, sorgunuzun 0,2 saniyede yürütülmesi ile saatler sürmesi arasındaki fark anlamına gelebilir.
Dikkate alınması gereken bir diğer husus da kötü bir algoritmanın iyileşme oranının az olmasıdır. Örneğin, O(n^3) olan bir bilimsel hesaplamanız varsa ve günde 100 şey hesaplayabiliyorsa, işlemci hızını iki katına çıkarmak size günde yalnızca 125 şey kazandırır. Ancak, bu hesaplamayı O(n^2)’ye düşürdüğünüzde günde 1000 şey yaparsınız.
Açıklama: Aslında Big-O, farklı algoritmaların aynı belirli boyut noktasındaki karşılaştırmalı performansından değil, aynı algoritmanın farklı boyut noktalarındaki karşılaştırmalı performansından bahseder:
Big-O | 10 şey | 100 şey | 1000 şey ---------------------------------------------------------------------- O(1) | 1 | 1 | 1 O(log(n)) | 1 | 3 | 7 O(n) | 1 | 10 | 100 O(n log(n)) | 1 | 33 | 664 O(n^2) | 1 | 100 | 10000
Zaman Karmaşıklığı’nın daha basit açıklaması
Zaman karmaşıklığını veya Big O notasyonunu anlamanın başka bir yolu da aşağıdaki gibi olabilir:
O(N^2), her bir eleman için, diğer her bir elemanla karşılaştırma gibi bir şey yaptığınız anlamına gelir. Bubble sort buna bir örnektir.
O(N log N), her öğe için yalnızca öğelerin log N’sine bakmanız gereken bir şey yaptığınız anlamına gelir. Bunun nedeni genellikle elemanlar hakkında verimli bir seçim yapmanızı sağlayacak bir şey biliyor olmanızdır. Birleştirme sıralaması gibi en verimli sıralamalar bunun bir örneğidir.
O(N!), N elemanın tüm olası permütasyonları için bir şey yapmak anlamına gelir. Traveling salesman (gezgin satıcı) bunun bir örneğidir, burada düğümleri ziyaret etmenin N! yolu vardır ve brute force çözümü, en uygun olanı bulmak için her olası permütasyonun toplam maliyetine bakmaktır.
O(n2), O(n), O(1) ve O(logN) Nedir?
Yukarıda söylediğimiz gibi bu notasyonlar bir algoritmanın girdi boyutuna göre nasıl ölçeklendiğini gösterir.
O(n2): Kuadratik karmaşıklık olarak bilinir
- 1 öğe: 1 işlem
- 10 öğe: 100 işlem
- 100 öğe: 10.000 işlem
Öğe sayısının 10 kat arttığına, ancak sürenin 10^2 kat arttığına dikkat edin. Temel olarak, n=10 ve dolayısıyla O(n2) bize 10^2 olan n^2 ölçekleme faktörünü verir.
O(n): Doğrusal karmaşıklık olarak bilinir
- 1 öğe: 1 işlem
- 10 madde: 10 işlem
- 100 madde: 100 işlem
Bu kez öğe sayısı 10 kat artar ve zaman da aynı oranda artar. n=10 ve dolayısıyla O(n)’nin ölçekleme faktörü 10’dur.
O(1): Sabit karmaşıklık olarak bilinir
- 1 öğe: 1 işlem
- 10 öğe: 1 işlem
- 100 öğe: 1 işlem
Öğe sayısı hala 10 kat artmakta, ancak O(1) ölçekleme faktörü ile işlem zamanı her zaman 1’dir.
O(log n): Logaritmik karmaşıklık olarak bilinir
- 1 öğe: 1 işlem
- 10 öğe: 2 işlem
- 100 öğe: 3 işlem
- 1000 öğe: 4 işlem
- 10,000 öğe: 5 işlem
Hesaplama sayısı yalnızca giriş değerinin logu kadar artar. Bu durumda, her bir hesaplamanın 1 saniye sürdüğü varsayıldığında, n girdinin logu gereken süredir, dolayısıyla log n’dir.
İşin özü aslında bu. Şimdi bunlara biraz daha detaylı bakalım ve sonrasında işin matematiğini inceleyelim.
Big O notasyonunun Detayları
BigO karmaşıklığını aşağıdaki grafik ile görselleştirebiliriz:
Big O notasyonu için verebileceğimiz en basit tanım şu olacaktır:
Big O notasyonu, bir algoritmanın karmaşıklığının göreceli bir temsilidir.
Bu cümlede bazı önemli ve bilinçli olarak seçilmiş kelimeler var:
- göreceli: sadece elmaları elmalarla karşılaştırabilirsiniz. Aritmetik çarpma işlemi yapan bir algoritma ile tam sayılar listesini sıralayan bir algoritmayı karşılaştıramazsınız. Ancak aritmetik işlem yapan iki algoritmanın (biri çarpma, biri toplama) karşılaştırılması size anlamlı bir şey söyleyebilir;
- temsil: BigOh (en basit haliyle) algoritmalar arasındaki karşılaştırmayı tek bir değişkene indirger. Bu değişken gözlemlere veya varsayımlara dayalı olarak seçilir. Örneğin, sıralama algoritmaları tipik olarak karşılaştırma işlemlerine (göreceli sıralamalarını belirlemek için iki düğümü karşılaştırma) dayalı olarak karşılaştırılır. Bu, karşılaştırmanın pahalı olduğunu varsayar. Peki ya karşılaştırma ucuz ama takas pahalıysa? Bu durumda karşılaştırmayı değiştirir; ve
- karmaşıklık: 10.000 öğeyi sıralamak bir saniyemi alıyorsa, bir milyon öğeyi sıralamam ne kadar sürer? Bu durumda karmaşıklık başka bir şeye göre göreceli bir ölçüdür.
Şimdi açıklamanın geri kalanı ile devam edelim ancak geri kalanı okuduktan sonra tekrar gelin ve yukarıdakileri tekrar okuyun.
Aklımıza gelebilecek en iyi BigO örneği aritmetik işlemler olacaktır. İki sayıyı ele alalım (123456 ve 789012). Okulda öğrendiğimiz temel aritmetik işlemler şunlardı:
- toplama;
- çıkarma;
- çarpma; ve
- bölme.
Bunların her biri bir işlem veya bir problem olarak sınıflandırılabilir. Bunları çözmenin bir yöntemine de algoritma denir.
Toplama işlemi en basit olanıdır. Rakamları sıraya dizersiniz (sağa doğru) ve rakamları bir sütunda toplarsınız ve bu toplamanın son rakamını sonuca yazarsınız. Bu sayının ‘onlar’ kısmı bir sonraki sütuna taşınır.
Bu sayıların toplanmasının bu algoritmadaki en pahalı işlem olduğunu varsayalım. Bu iki sayıyı toplamak için 6 basamağı bir araya getirmemiz (ve muhtemelen 7. basamağı taşımamız) gerektiği mantıklıdır. Eğer 100 basamaklı iki sayıyı toplarsak 100 toplama işlemi yapmamız gerekir. Eğer 10.000 basamaklı iki sayıyı toplarsak 10.000 toplama işlemi yapmamız gerekir.
Buradaki şablonu görüyor musunuz? Karmaşıklık (işlem sayısı olarak) daha büyük sayıdaki n basamak sayısı ile doğru orantılıdır. Buna O(n) veya doğrusal karmaşıklık diyoruz.
Çıkarma işlemi de benzerdir (ancak taşıma yerine ödünç almanız gerekebilir).
Çarpma işlemi farklıdır. Sayıları sıraya dizersiniz, alttaki sayının ilk rakamını alırsınız ve sırayla üstteki sayının her bir rakamıyla çarparsınız ve bu şekilde her bir rakam boyunca devam edersiniz. Yani 6 basamaklı iki sayımızı çarpmak için 36 çarpma işlemi yapmamız gerekir. Sonuca ulaşmak için 10 ya da 11 sütun eklemesi de yapmamız gerekebilir.
Eğer 100 basamaklı iki sayımız varsa 10.000 çarpma ve 200 toplama işlemi yapmamız gerekir. Bir milyon basamaklı iki sayı için bir trilyon (10^12) çarpma ve iki milyon toplama işlemi yapmamız gerekir.
Algoritma n-kare ile ölçeklendiğinden, bu O(n2) veya ikinci dereceden karmaşıklıktır.
Şimdi, başka bir önemli kavramı tanımak için devam edelim:
Biz sadece karmaşıklığın en önemli kısmıyla ilgileniyoruz.
Dikkatli olanlar işlem sayısını n^2 + 2n şeklinde ifade edebileceğimizi fark etmiş olabilirler. Ancak her biri bir milyon basamaklı iki sayı içeren örneğimizde gördüğünüz gibi, ikinci terim (2n) artık önemsiz hale gelir (o aşamaya kadar toplam işlemlerin %0,0002’sini oluşturur).
Burada en kötü durum senaryosunu varsaydığımızı fark edebilirsiniz. 6 basamaklı sayıları çarparken, bunlardan biri 4 basamaklı ve diğeri 6 basamaklı ise, o zaman sadece 24 çarpma işlemimiz olur. Yine de, bu ‘n’ için, yani her ikisi de 6 basamaklı sayı olduğunda en kötü senaryoyu hesaplıyoruz. Dolayısıyla Big O notasyonu bir algoritmanın en kötü durum senaryosuyla ilgilidir.
Telefon Rehberi
Aklımıza gelecek bir sonraki en iyi örnek, normalde Sarı Sayfalar veya benzeri olarak adlandırılan telefon rehberleridir. Burada insanları önce soyadlarına, sonra baş harflerine ya da adlarına, muhtemelen adreslerine ve sonra da telefon numaralarına göre listeleyen telefon rehberlerini düşünüyoruz.
Şimdi bir bilgisayara 1.000.000 isim içeren bir telefon rehberinde “John Smith” için telefon numarasını araması talimatını verseydiniz ne yapardınız? S’lerin ne kadar ileriden başladığını tahmin edebileceğiniz gerçeğini göz ardı ederek (edemeyeceğinizi varsayalım), ne yapardınız?
Tipik bir uygulama rehberi tam ortadan açmak, 500.000’inciyi almak ve “Smith” ile karşılaştırmak olabilir. Eğer “Smith, John” çıkarsa, gerçekten şanslıyız demektir. “John Smith “in bu isimden önce ya da sonra olması çok daha olasıdır. Eğer sonraysa, telefon rehberinin son yarısını ikiye böleriz ve tekrar ederiz. Eğer önceyse, telefon rehberinin ilk yarısını ikiye böleriz ve tekrar ederiz. Ve böylece devam ederiz.
Buna ikili arama denir ve farkında olsanız da olmasanız da programlamada her gün kullanılır.
Yani bir milyon isimden oluşan bir telefon rehberinde bir ismi bulmak istiyorsanız, aslında bunu en fazla 20 kez yaparak herhangi bir ismi bulabilirsiniz. Arama algoritmalarını karşılaştırırken bu karşılaştırmanın bizim ‘n’ değerimiz olduğuna karar veriyoruz.
- Üç isimden oluşan bir telefon rehberi için (en fazla) 2 karşılaştırma gerekir.
- 7 için en fazla 3 gerekir.
- 15 için 4 gerekir.
- …
- 1,000,000 için 20 gerekiyor.
Şaşırtıcı derecede iyi, değil mi?
BigO terimleriyle bu O(log n) veya logaritmik karmaşıklıktır. Şimdi söz konusu logaritma ln (e tabanı), log10, log2 veya başka bir taban olabilir. Fark etmez, yine de O(log n)’dir, tıpkı O(2n^2) ve O(100n^2)’nin her ikisinin de O(n^2) olması gibi.
Bu noktada BigO’nun bir algoritma ile üç durumu belirlemek için kullanılabileceğini açıklamakta fayda var:
- En İyi Durum: Telefon rehberi aramasında en iyi durum, ismi tek bir karşılaştırmada bulmamızdır. Bu O(1) veya sabit karmaşıklıktır;
- Beklenen Durum: Yukarıda tartışıldığı gibi bu O(log n)’dir; ve
- En Kötü Durum: Bu da O(log n)’dir.
Normalde en iyi durumla ilgilenmeyiz. Beklenen ve en kötü durumla ilgileniriz. Bazen bunlardan biri ya da diğeri daha önemli olabilir.
Telefon rehberine geri dönelim.
Elinizde bir telefon numarası varsa ve bir isim bulmak istiyorsanız ne olacak? Teknik olarak sıradan bir telefon rehberindeki bir numarayı tersine arayabilirsiniz. Nasıl?
İlk isimden başlar ve numarayı karşılaştırırsınız. Eşleşirse harika, eşleşmezse bir sonrakine geçersiniz. Bunu bu şekilde yapmak zorundasınız çünkü telefon rehberi sırasızdır (en azından telefon numarasına göre).
Yani telefon numarası verilen bir ismi bulmak için (ters arama):
- En iyi durum: O(1);
- Beklenen Durum: O(n) (500.000 için); ve
- En Kötü Durum: O(n) (1.000.000 için).
The Traveling Salesman – Gezgin Satıcı
Bu, bilgisayar bilimlerinde oldukça ünlü bir problemdir ve burada bahsedilmeyi hak ediyor. Bu problemde N tane kasabanız var. Bu kasabaların her biri 1 veya daha fazla diğer kasabaya belirli bir mesafedeki bir yol ile bağlı. Gezgin Satıcı probleminde sorun, her kasabayı ziyaret eden en kısa turu bulmaktır.
Basit gibi değil mi? Tekrar düşünelim.
Eğer A, B ve C olmak üzere 3 kasabanız varsa ve her çift arasında yol varsa, o zaman aşağıdakini yapabilirsiniz:
- A → B → C
- A → C → B
- B → C → A
- B → A → C
- C → A → B
- C → B → A
Aslında bundan daha da azını göz önünde bulundurmamız yeterlidir. Çünkü bunlardan bazıları eşdeğerdir (örneğin A → B → C ve C → B → A eşdeğerdir, çünkü aynı yolları kullanırlar, sadece tersten). Gerçekte, 3 olasılık bulunur.
- Bunu 4 şehre çıkardığınızda 12 olasılığınız olur.
- 5 ile 60.
- 6 ile 360 olur.
Bu, faktöriyel adı verilen matematiksel bir işlemin bir fonksiyonudur. Temel olarak:
- 5! = 5 × 4 × 3 × 2 × 1 = 120
- 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
- 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
- …
- 25! = 25 × 24 × … × 2 × 1 = 15,511,210,043,330,985,984,000,000
- …
- 50! = 50 × 49 × … × 2 × 1 = 3.04140932 × 1064
Yani Gezgin Satıcı probleminin BigO’su O(n!) ya da faktöriyel veya kombinatoryal karmaşıklıktır.
Siz 200 kasabaya ulaştığınızda, evrende geleneksel bilgisayarlarla sorunu çözmek için yeterli zaman kalmamıştır (Bu bazılarımız için üzerinde düşünülecek bir şey olabilir).
Şimdi işin matematiğine bakalım.
Big O’nun Matematiği
Big-O notasyonu (“asimptotik büyüme” notasyonu olarak da adlandırıldığını söylemiştik), sabit faktörleri ve orijin yakınındaki şeyleri göz ardı ettiğinizde fonksiyonların “nasıl göründüğüdür”. Bir şeyin nasıl ölçeklendiği hakkında konuşmak için kullanırız.
Temeller
“yeterince” büyük girdiler için…
- f(x) ∈ O(üst sınır), f’nin üst sınırdan “daha hızlı büyümediği” anlamına gelir
- f(x) ∈ Ɵ(aa) f’nin “tam olarak aa gibi büyüdüğü” anlamına gelir
- f(x) ∈ Ω(alt sınır), f’nin alt sınırdan “daha yavaş büyümediği” anlamına gelir
big-O gösterimi sabit faktörleri önemsemez: 9x² fonksiyonunun “tam olarak 10x² gibi büyüdüğü” söylenir. Big-O asimptotik gösterimi de asimptotik olmayan şeyleri (“orijine yakın şeyler” veya “problem boyutu küçük olduğunda ne olur”) önemsemez: 10x² fonksiyonunun “tam olarak 10x² – x + 2 gibi büyüdüğü” söylenir.
Denklemin küçük parçalarını neden göz ardı etmek isteyesiniz ki? Çünkü daha büyük ölçekleri göz önünde bulundurduğunuzda denklemin büyük kısımları tarafından tamamen cüceleştirilirler; katkıları cüceleşir ve önemsiz hale gelir. (Örnek bölümüne bakın.)
Başka bir deyişle, sonsuza giderken her şey oranla ilgilidir. Gerçekte geçen süreyi O(…) ile bölerseniz, büyük girdilerin sınırında sabit bir faktör elde edersiniz. Sezgisel olarak da bu mantıklıdır: eğer birini çarparak diğerini elde edebiliyorsanız, fonksiyonlar birbirleri gibi “ölçeklenir”. İşte o zaman şöyle deriz.
AlgoritmaZamanı(N) ∈ O(bound(N))
ör. "N elemanı birleştirme zamanı O(N log(N))"… bu, “yeterince büyük” problem boyutları N için (orijine yakın şeyleri göz ardı edersek), öyle bir sabitin (örneğin 2.5, tamamen uydurma) var olduğu anlamına gelir:
AlgoritmaZamanı(N) ör. "mergesort_zamanı(N)"
────────────────────── < sabit ───────────────────── < 2.5
bound(N) N log(N)
Birçok sabit seçeneği vardır; genellikle “en iyi” seçim algoritmanın “sabit faktörü” olarak bilinir… ancak genellikle en büyük olmayan terimleri görmezden geldiğimiz gibi bunu da görmezden geliriz (neden genellikle önemli olmadıkları için Sabit Faktörler bölümüne bakın). Yukarıdaki denklemi bir sınır olarak da düşünebilirsiniz: “En kötü senaryoda, geçen süre hiçbir zaman kabaca N*log(N)’den daha kötü olmayacaktır (2,5 faktörü içinde, çok fazla önemsemediğimiz bir sabit faktör)”.
Genel olarak, O(…) en kullanışlı olanıdır çünkü genellikle en kötü durum davranışını önemseriz. Eğer f(x) işlemci veya bellek kullanımı gibi “kötü” bir şeyi temsil ediyorsa, “f(x) ∈ O(upperbound)” “upperbound işlemci/bellek kullanımının en kötü senaryosudur” anlamına gelir.
Uygulamalar
Tamamen matematiksel bir yapı olan big-O notasyonu, işlem süresi ve bellek hakkında konuşmakla sınırlı değildir. Ölçeklemenin anlamlı olduğu herhangi bir şeyin asimptotiğini tartışmak için kullanabilirsiniz, örneğin:
- bir partide N kişi arasında olası el sıkışma sayısı (Ɵ(N²), özellikle N(N-1)/2, ancak önemli olan N² gibi “ölçeklenmesi”)
- zamanın bir fonksiyonu olarak bazı viral pazarlamaları gören kişilerin olasılıksal beklenen sayısı
- web sitesi gecikmesinin bir CPU veya GPU ya da bilgisayar kümesindeki işlem birimi sayısıyla nasıl ölçeklendiği
- transistör sayısı, voltaj vb. faktörlerin bir fonksiyonu olarak CPU kalıplarında ısı çıkışının nasıl ölçeklendiği
- girdi boyutunun bir fonksiyonu olarak bir algoritmanın çalışması için ne kadar zaman gerektiği
- girdi boyutunun bir fonksiyonu olarak bir algoritmanın çalışması için ne kadar alana ihtiyaç duyduğu
Örnekler
Yukarıdaki el sıkışma örneğinde, bir odadaki herkes birbirinin elini sıkar. Bu örnekte, #elsıkma ∈ Ɵ(N²). Neden?
Biraz geri gidelim: el sıkışma sayısı tam olarak n-seç-2 veya N*(N-1)/2’dir (N kişinin her biri N-1 kişinin elini sıkar, ancak bu el sıkışmaları iki katına çıkarır, bu nedenle 2’ye böleriz):
Ancak, çok büyük sayıda insan için doğrusal N terimi cüce kalır ve orana etkin bir şekilde 0 katkıda bulunur (grafikte: köşegendeki boş kutuların toplam kutulara oranı katılımcı sayısı arttıkça küçülür). Bu nedenle ölçekleme davranışı N² mertebesindedir ya da el sıkışma sayısı “N² gibi büyür”.
#elsıkma(N)
────────────── ≈ 1/2
N²
Sanki grafiğin köşegenindeki boş kutular orada yokmuş gibi.
Bunu kendinize kanıtlamak isterseniz, oran üzerinde bazı basit cebir işlemleri yaparak onu birden fazla terime ayırabilirsiniz (lim, “limitinde düşünülür” anlamına gelir, limit ile ilgilenmiyorsanız bu kısmı görmezden gelin, bu sadece “ve N gerçekten çok büyük” için bir notasyondur):
N²/2 - N/2 (N²)/2 N/2 1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞ N² N→∞ N² N² N→∞ 1
┕━━━┙
N→∞ limitinde bu değer 0'dır:
Sezgi Geliştirme
Bu, şu gibi ifadeler kullanmamızı sağlar.
“Yeterince büyük girdi boyutu=N için, sabit faktör ne olursa olsun, girdi boyutunu iki katına çıkarırsam…
- … O(N) (“doğrusal zaman”) algoritmasının süresini iki katına çıkarıyorum.”
N → (2N) = 2(N)
- … Bir O(N²) (“ikinci dereceden zaman”) algoritmasının aldığı zamanı iki*iki katına çıkardım (dört katına çıkardım).” (örneğin 100 kat daha büyük bir problem 100²=10000 kat daha uzun sürer… muhtemelen çalıştırılmaz)
N² → (2N)² = 4(N²)
- … Bir O(N³) (“kübik zaman”) algoritmasının aldığı zamanı iki^üç katına çıkardım (sekiz katına).” (örneğin, 100 kat daha büyük bir problem 100³=1000000 kat daha uzun sürer… muhtemelen çok çalıştırılmaz)
cN³ → c(2N)³ = 8(cN³)
- … Bir O(log(N)) (“logaritmik zaman”) algoritmasının aldığı zamana sabit bir miktar ekliyorum.” (ucuz!)
c log(N) → c log(2N) = (c log(2))+(c log(N)) = (sabit miktar)+(c log(N))
- … O(1) (“sabit zamanlı”) bir algoritmanın aldığı süreyi değiştirmiyorum.” (en ucuzu!)
c*1 → c*1
- … Bir O(N log(N)) algoritmasının aldığı zamanı “(temelde) iki katına çıkarırım.” (oldukça yaygın)
c 2N log(2N) / c N log(N) (Burada f(2n)/f(n)’e bölüyoruz, ancak yukarıdaki gibi ifadeyi değiştirebilir ve cNlogN’i yukarıdaki gibi çarpanlarına ayırabilirdik)
→ 2 log(2N)/log(N)
→ 2 (log(2) + log(N))/log(N)
→ 2*(1+(log2N)-1) (büyük N için temelde 2; sonuçta 2.000001’den daha az)
(Alternatif olarak, log(N)’nin sizin verileriniz için her zaman 17’nin altında olacağını, dolayısıyla doğrusal olan O(17 N) olduğunu söyleyin; ancak bu ne sağlamdır ne de mantıklıdır)
- … O(2^N) (“üstel zaman”) algoritmasının süresini gülünç bir şekilde artırıyorum.” (sadece problemi tek bir birim artırarak süreyi iki katına (veya üç katına, vb.) çıkarırsınız)
2N → 22N = (4N)…………veya…… 2N → 2N+1 = 2N21 = 2 2N
Bunlar, programcıların ve uygulamalı bilgisayar bilimcilerinin referans noktası olarak kullandıkları temel büyüme sıralarıdır. Bunları her zaman görürüz. (Yani teknik olarak “Girdiyi iki katına çıkarmak bir O(√N) algoritmasını 1,414 kat yavaşlatır” diye düşünebilirsiniz, ancak bunu “bu logaritmikten daha kötü ama doğrusaldan daha iyi” olarak düşünmek daha iyidir).
Sabit faktörler
Genellikle, belirli sabit faktörlerin ne olduğu umurumuzda değildir, çünkü bunlar fonksiyonun büyüme şeklini etkilemez. Örneğin, iki algoritmanın her ikisinin de tamamlanması O(N) zaman alabilir, ancak biri diğerinden iki kat daha yavaş olabilir. Optimizasyon zor bir iş olduğundan, faktör çok büyük olmadıkça genellikle çok fazla önemsemeyiz; ayrıca daha iyi bir big-O’ya sahip bir algoritma seçme eylemi genellikle performansı büyüklük sırasına göre artıracaktır.
Bazı asimptotik olarak üstün algoritmalar (örneğin karşılaştırmasız O(N log(log(N)) sıralama) o kadar büyük bir sabit faktöre (örneğin 100000N log(log(N))) veya gizli + 100N ile O(N log(log(N)) gibi nispeten büyük bir ek yüke sahip olabilir ki “büyük verilerde” bile nadiren kullanılmaya değerdir.
Neden O(N) bazen yapabileceğinizin en iyisidir, yani neden veri yapılarına ihtiyacımız var?
O(N) algoritmaları, tüm verilerinizi okumanız gerekiyorsa bir anlamda “en iyi” algoritmalardır. Bir grup veriyi okuma eylemi bir O(N) işlemidir. Hafızaya yüklemek genellikle O(N)’dir (ya da donanım desteğiniz varsa daha hızlıdır veya verileri zaten okuduysanız hiç zaman almaz). Ancak, her bir veri parçasına (hatta her bir diğer veri parçasına) dokunur ya da bakarsanız, algoritmanızın bu bakma işlemini gerçekleştirmesi O(N) zaman alacaktır. Gerçek algoritmanız ne kadar uzun sürerse sürsün, bu süre en az O(N) olacaktır çünkü bu süreyi tüm verilere bakarak geçirmiştir.
Aynı şey yazma eylemi için de söylenebilir. N şeyi yazdıran tüm algoritmalar N zaman alacaktır çünkü çıktı en az bu kadar uzundur (örneğin, N oyun kartı setinin tüm permütasyonlarını (yeniden düzenleme yolları) yazdırmak faktöriyeldir: O(N!) (bu nedenle bu gibi durumlarda iyi programlar bir iterasyonun O(1) bellek kullanmasını sağlar ve her ara adımı yazdırmaz veya saklamaz).
Bu, veri yapılarının kullanımını motive eder: bir veri yapısı, verinin yalnızca bir kez okunmasını (genellikle O(N) zaman) ve ayrıca küçük tutmaya çalıştığımız isteğe bağlı bir miktar ön işlem (örneğin O(N) veya O(N log(N)) veya O(N²)) gerektirir. Bundan sonra, veri yapısını değiştirmek (ekleme/silme/ vb.) ve veriler üzerinde sorgu yapmak O(1) veya O(log(N)) gibi çok az zaman alır. Daha sonra çok sayıda sorgu yapmaya devam edersiniz! Genel olarak, önceden ne kadar çok iş yapmaya istekli olursanız, daha sonra o kadar az iş yapmanız gerekir.
Örneğin, milyonlarca yol parçasının enlem ve boylam koordinatlarına sahip olduğunuzu ve tüm sokak kesişimlerini bulmak istediğinizi varsayalım.
- Saf yöntem: Bir cadde kesişiminin koordinatlarına sahipseniz ve yakındaki caddeleri incelemek istiyorsanız, her seferinde milyonlarca segmenti gözden geçirmeniz ve her birini bitişiklik açısından kontrol etmeniz gerekir.
- Bunu yalnızca bir kez yapmanız gerekiyorsa, naif yöntem olan O(N) işini yalnızca bir kez yapmak sorun olmaz, ancak bunu birçok kez yapmak istiyorsanız (bu durumda, her segment için bir kez olmak üzere N kez), O(N²) işi veya 1000000²=1000000000000 işlem yapmamız gerekir. Bu iyi değil (modern bir bilgisayar saniyede yaklaşık bir milyar işlem gerçekleştirebilir).
- Hash tablosu (anlık hızlı arama tablosu, hashmap veya sözlük olarak da bilinir) adı verilen basit bir yapı kullanırsak, her şeyi O(N) zamanında ön işleme tabi tutarak küçük bir maliyet öderiz. Bundan sonra, bir şeyi anahtarına göre aramak ortalama olarak sadece sabit zaman alır (bu durumda, anahtarımız bir ızgaraya yuvarlanmış enlem ve boylam koordinatlarıdır; sadece 9 tane olan bitişik ızgara alanlarını ararız, bu da bir sabittir).
- Görevimiz makul olmayan bir O(N²)’den kontrol edilebilir bir O(N)’ye düştü ve tek yapmamız gereken bir hash tablosu oluşturmak için küçük bir maliyet ödemekti.
- Analoji: Bu özel durumdaki analoji bir yapbozdur: Verilerin bazı özelliklerinden yararlanan bir veri yapısı oluşturduk. Yol segmentlerimiz yapboz parçaları gibiyse, onları renk ve desen eşleşmesine göre gruplandırırız. Daha sonra fazladan iş yapmaktan kaçınmak için bundan yararlanırız (benzer renkteki yapboz parçalarını diğer tüm yapboz parçalarıyla değil birbirleriyle karşılaştırarak).
Kıssadan hisse: bir veri yapısı işlemleri hızlandırmamızı sağlar. Daha da ötesi, gelişmiş veri yapıları işlemleri inanılmaz zekice yollarla birleştirmenize, geciktirmenize ve hatta yok saymanıza izin verebilir. Farklı sorunların farklı analojileri olacaktır, ancak hepsi de verileri önemsediğimiz ya da muhasebe için yapay olarak dayattığımız bazı yapılardan yararlanacak şekilde düzenlemeyi içerir. İşi önceden yaparız (temelde planlama ve organize etme) ve artık tekrarlanan görevler çok daha kolaydır!
Pratik örnek: kodlama yaparken büyüme oranlarını görselleştirme
Asimptotik gösterim, özünde programlamadan oldukça ayrıdır. Asimptotik gösterim, nesnelerin nasıl ölçeklendiğini düşünmek için matematiksel bir çerçevedir ve birçok farklı alanda kullanılabilir. Bununla birlikte… asimptotik notasyonu kodlamaya şu şekilde uygularsınız.
Temel bilgiler: A boyutundaki bir koleksiyondaki (dizi, küme, haritanın tüm anahtarları vb.) her bir elemanla etkileşime girdiğimizde veya bir döngünün A yinelemesini gerçekleştirdiğimizde, bu A boyutunun çarpımsal bir faktörüdür. Neden “çarpımsal bir faktör” diyorum? Çünkü döngüler ve fonksiyonlar (neredeyse tanım gereği) çarpımsal çalışma süresine sahiptir: yineleme sayısı, çarpı döngüde yapılan iş (veya fonksiyonlar için: fonksiyonu çağırma sayısı, çarpı fonksiyonda yapılan iş). (Bu, döngüleri atlamak veya döngüden erken çıkmak gibi süslü bir şey yapmazsak veya işlevdeki kontrol akışını argümanlara göre değiştirmezsek geçerlidir, ki bu çok yaygındır). Görselleştirme tekniklerine ilişkin bazı örneklere ve bunlara eşlik eden kodlara bakalım.
(burada x’ler sabit zamanlı iş birimlerini, işlemci talimatlarını, yorumlayıcı işlem kodlarını, vb temsil eder)
for(i=0; i<A; i++) // A * ...
bir takım O(1) işlem // 1
--> A*1 --> O(A) time
görselleştirme:
|<------ A ------->|
1 2 3 4 5 x x ... x
Diğer diller:
javascript, O(A) time and space
someListOfSizeA.map((x,i) => [x,i])
python, O(rows*cols) zaman and alan
[[r*c for c in range(cols)] for r in range(rows)]
Örnek 2:
for every x in listOfSizeA: // A * (...
bir takım O(1) işlem // 1
bir takım O(B) işlem // B
for every y in listOfSizeC: // C * (...
bir takım O(1) işlem // 1))
--> O(A*(1 + B + C))
O(A*(B+C)) (1 cüceleşti)
görsel:
|<------ A ------->|
1 x x x x x x ... x
2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v
x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v
Örnek 3:
function nSquaredFunction(n) {
total = 0
for i in 1..n: // N *
for j in 1..n: // N *
total += i*k // 1
return total
}
// O(n^2)
function nCubedFunction(a) {
for i in 1..n: // A *
print(nSquaredFunction(a)) // A^2
}
// O(a^3)
Biraz karmaşık bir şey yapsak bile, yine de neler olup bittiğini görsel olarak hayal edebilirsiniz:
for x in range(A):
for y in range(1..x):
simpleOperation(x*y)
x x x x x x x x x x |
x x x x x x x x x |
x x x x x x x x |
x x x x x x x |
x x x x x x |
x x x x x |
x x x x |
x x x |
x x |
x___________________|
Burada önemli olan çizebileceğiniz en küçük tanınabilir taslaktır; bir üçgen iki boyutlu bir şekildir (0,5 A^2), tıpkı bir karenin iki boyutlu bir şekil (A^2) olması gibi; burada iki sabit faktörü ikisi arasında asimptotik oranda kalır, ancak tüm faktörler gibi onu da göz ardı ederiz… (Bu tekniğin burada girmediğim bazı talihsiz nüansları var; sizi yanlış yönlendirebilir).
Elbette bu, döngülerin ve fonksiyonların kötü olduğu anlamına gelmez; tam tersine, bunlar modern programlama dillerinin yapı taşlarıdır ve onları seviyoruz. Ancak, döngüleri, fonksiyonları ve koşulluları verilerimizle birlikte örme şeklimizin (kontrol akışı vb.) programımızın zaman ve alan kullanımını taklit ettiğini görebiliriz! Zaman ve alan kullanımı bir sorun haline gelirse, işte o zaman zekaya başvurur ve büyüme sırasını bir şekilde azaltmak için düşünmediğimiz kolay bir algoritma veya veri yapısı buluruz. Yine de, bu görselleştirme teknikleri (her zaman işe yaramasa da) size en kötü durum çalışma süresi hakkında naif bir tahmin verebilir.
Görsel olarak tanıyabileceğimiz bir başka şeye bakalım:
<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x
Bunu yeniden düzenleyebilir ve O(N) olduğunu görebiliriz:
<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x
Ya da belki O(N*log(N)) toplam zaman için verilerin log(N) geçişlerini yaparsınız:
<----------------------------- N ----------------------------->
^ x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
| x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
| x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
v x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x
İlgisiz ama tekrar bahsetmeye değer: Eğer bir hash (örneğin bir sözlük/hashtable araması) gerçekleştirirsek, bu O(1) katsayısıdır. Ve oldukça hızlıdır.
[myDictionary.has(x) for x in listOfSizeA]
\----- O(1) ------/
--> A*1 --> O(A)
Ancak programcılar böyle düşünmezler çünkü sonunda algoritma sezgisi ikinci doğanız haline gelir. Verimsiz bir şey kodlamaya başlarsınız ve hemen “fena halde verimsiz bir şey mi yapıyorum?” diye düşünürsünüz. Cevap “evet” ise VE bunun gerçekten önemli olduğunu öngörüyorsanız, o zaman bir adım geri atabilir ve işlerin daha hızlı çalışmasını sağlamak için çeşitli hileler düşünebilirsiniz (cevap neredeyse her zaman “bir hashtable kullanın”, nadiren “bir ağaç kullanın” ve çok nadiren biraz daha karmaşık bir şeydir).
Amorti edilmiş ve ortalama durum karmaşıklığı
Ayrıca “amorti edilmiş” ve/veya “ortalama vaka” kavramı da vardır (bunların farklı olduğunu unutmayın).
Ortalama Durum: Bu, bir fonksiyonun kendisi yerine beklenen değeri için big-O notasyonunu kullanmaktan başka bir şey değildir. Tüm girdilerin eşit olasılıkta olduğunu düşündüğünüz olağan durumda, ortalama durum sadece çalışma süresinin ortalamasıdır. Örneğin quicksort ile, bazı gerçekten kötü girdiler için en kötü durum O(N^2) olsa da, ortalama durum normal O(N log(N))’dir (gerçekten kötü girdiler sayıca çok azdır, ortalama durumda onları fark etmeyeceğimiz kadar azdır).
Amorti Edilmiş En Kötü Durum: Bazı veri yapıları büyük bir en kötü durum karmaşıklığına sahip olabilir, ancak bu işlemlerin çoğunu yaparsanız, yaptığınız ortalama iş miktarının en kötü durumdan daha iyi olacağını garanti eder. Örneğin, normalde sabit O(1) zaman alan bir veri yapınız olabilir. Ancak, zaman zaman ‘hıçkırır’ ve rastgele bir işlem için O(N) zaman alır, çünkü belki bazı defter tutma veya çöp toplama veya başka bir şey yapması gerekir… ancak hıçkırırsa, N işlem için tekrar hıçkırmayacağına dair size söz verir. En kötü durum maliyeti hala işlem başına O(N)’dir, ancak birçok çalıştırma boyunca amorti edilen maliyet işlem başına O(N)/N = O(1)’dir. Büyük işlemler yeterince nadir olduğu için, ara sıra yapılan büyük miktardaki işin, sabit bir faktör olarak işin geri kalanıyla karıştığı düşünülebilir. İşin, asimptotik olarak kaybolacak kadar çok sayıda çağrı üzerinde “amorti edildiğini” söylüyoruz.
Amortisman analizi için benzetme:
Bir araba kullanıyorsunuz. Ara sıra benzin istasyonuna gitmek için 10 dakika harcamanız ve ardından depoyu benzinle doldurmak için 1 dakika harcamanız gerekiyor. Bunu arabanızla her yere gittiğinizde yapsaydınız (benzin istasyonuna gitmek için 10 dakika harcamak, bir galonun bir kısmını doldurmak için birkaç saniye harcamak), bu çok verimsiz olurdu. Ancak depoyu birkaç günde bir doldurursanız, benzin istasyonuna gitmek için harcadığınız 11 dakika yeterince fazla sayıda yolculuğa “amorti” edilir, böylece bunu görmezden gelebilir ve tüm yolculuklarınız belki %5 daha uzunmuş gibi davranabilirsiniz.
Ortalama durum ile amorti edilmiş en kötü durum arasında karşılaştırma:
- Ortalama durum: Girdilerimiz hakkında bazı varsayımlarda bulunuruz; yani girdilerimiz farklı olasılıklara sahipse, çıktılarımız/çalışma sürelerimiz de farklı olasılıklara sahip olacaktır (bunların ortalamasını alırız). Genellikle, girdilerimizin hepsinin eşit olasılıkta (tekdüze olasılık) olduğunu varsayarız, ancak gerçek dünyadaki girdiler “ortalama girdi” varsayımlarımıza uymuyorsa, ortalama çıktı/çalışma süresi hesaplamaları anlamsız olabilir. Yine de tekdüze rastgele girdiler bekliyorsanız, bunu düşünmek faydalı olacaktır!
- Amorti edilmiş en kötü durum: Amorti edilmiş en kötü durum veri yapısı kullanırsanız, performansın eninde sonunda amorti edilmiş en kötü durum dahilinde olacağı garanti edilir (girdiler her şeyi bilen ve sizi kazıklamaya çalışan kötü bir şeytan tarafından seçilmiş olsa bile). Genellikle bunu, beklenmedik büyük hıçkırıklarla performansta çok ‘dalgalı’ olabilen, ancak zaman içinde diğer algoritmalar kadar iyi performans gösteren algoritmaları analiz etmek için kullanırız. (Bununla birlikte, veri yapınızın ertelemeye istekli olduğu çok sayıda bekleyen iş için üst sınırları yoksa, kötü bir saldırgan belki de sizi bir kerede ertelenen maksimum iş miktarını yakalamaya zorlayabilir.
Hem ortalama durum hem de amortisman, ölçeklendirmeyi göz önünde bulundurarak düşünmek ve tasarlamak için inanılmaz derecede yararlı araçlardır.
Matematik ekleri
Bu kısım ilginizi çekmiyorsa atlayabilirsiniz.
Bütünlük için, big-O gösteriminin tam tanımı şöyledir: f(x) ∈ O(g(x)), “f asimptotik olarak const*g ile üst sınırlıdır” anlamına gelir: x’in bazı sonlu değerlerinin altındaki her şeyi göz ardı ederek, |f(x)| ≤ const * |g(x)| olacak şekilde bir sabit vardır. (Diğer semboller aşağıdaki gibidir: tıpkı O’nun ≤ anlamına gelmesi gibi, Ω da ≥ anlamına gelir. Küçük harf varyantları vardır: o < ve ω > anlamına gelir.) f(x) ∈ Ɵ(g(x)) hem f(x) ∈ O(g(x)) hem de f(x) ∈ Ω(g(x)) (g tarafından üst ve alt sınırlanmış) anlamına gelir: f’nin her zaman const1g(x) ve const2g(x) arasındaki “bantta” yer alacağı bazı sabitler vardır. Bu, yapabileceğiniz en güçlü asimptotik ifadedir ve kabaca ==’e eşdeğerdir.
İnsanlar genellikle = O(…) kullanırlar, bu belki de daha doğru ‘comp-sci’ gösterimidir ve kullanımı tamamen meşrudur; “f = O(…)”, “f … mertebesindedir / f … ile sınırlıdır” şeklinde okunur ve “f, asimptotikleri … / f xxx-sınırlı …” şeklinde okunur ve “f asimptotikleri … olan bir ifadedir” şeklinde düşünülür. Daha titizseniz ∈ O(…) kullanırsınız. ∈ “bir elemanıdır” anlamına gelir (yine önceki gibi okunur). Bu özel durumda, O(N²) {2 N², 3 N², 1/2 N², 2 N² + log(N), – N² + N^1.9, …} gibi elemanlar içerir ve sonsuz büyüklüktedir, ancak yine de bir kümedir.
O ve Ω simetrik değildir (n = O(n²), ancak n² O(n) değildir), ancak Ɵ simetriktir ve (bu ilişkilerin tümü geçişli ve dönüşlü olduğundan) Ɵ, bu nedenle, simetrik ve geçişli ve dönüşlüdür ve bu nedenle tüm fonksiyonlar kümesini denklik sınıflarına böler. Bir denklik sınıfı, aynı olduğunu düşündüğümüz şeylerin bir kümesidir. Yani, aklınıza gelebilecek herhangi bir fonksiyon verildiğinde, sınıfın kanonik / benzersiz bir ‘asimptotik temsilcisini’ bulabilirsiniz (genellikle limiti alarak… sanırım); tıpkı tüm tam sayıları tek veya çift olarak gruplayabildiğiniz gibi, Ɵ ile tüm fonksiyonları x-ish, log(x)^2-ish, vb… temelde daha küçük terimleri göz ardı ederek gruplayabilirsiniz (ancak bazen kendi başlarına ayrı sınıflar olan daha karmaşık fonksiyonlarla sıkışıp kalabilirsiniz).
= gösterimi daha yaygın olabilir ve dünyaca ünlü bilgisayar bilimcilerinin makalelerinde bile kullanılır. Ayrıca, sıradan bir ortamda insanlar Ɵ(…) demek istediklerinde genellikle O(…) derler; bu teknik olarak doğrudur çünkü Ɵ(exactlyThis) kümesi O(noGreaterThanThis)’in bir alt kümesidir… ve yazması daha kolaydır ;).
Çok boyutlu big-O
Çoğu zaman insanlar birden fazla değişkenin söz konusu olduğunu fark etmezler. Örneğin, bir dize arama algoritmasında, algoritmanız O([metnin uzunluğu] + [sorgunun uzunluğu]) zaman alabilir, yani O(N+M) gibi iki değişkende doğrusaldır. Diğer daha naif algoritmalar O([metin uzunluğu][sorgu uzunluğu]) veya O(NM) olabilir. Birden fazla değişkeni göz ardı etmek, algoritma analizinde görülebilecek en yaygın dikkatsizliklerden biridir ve bir algoritma tasarlarken sizi handikaplı hale getirebilir.
Zaman Karmaşıklığında Hikayenin Tamamı
Big-O’nun hikayenin tamamı olmadığını unutmayın. Önbellek kullanarak, önbellekten bağımsız hale getirerek, disk yerine RAM ile çalışarak darboğazlardan kaçınarak, paralelleştirme kullanarak veya işi önceden yaparak bazı algoritmaları büyük ölçüde hızlandırabilirsiniz – bu teknikler genellikle büyüme sırası “big-O” gösteriminden bağımsızdır, ancak paralel algoritmaların big-O gösteriminde genellikle çekirdek sayısını görürsünüz.
Ayrıca, programınızın gizli kısıtlamaları nedeniyle asimptotik davranışı gerçekten önemsemeyebileceğinizi unutmayın. Örneğin, sınırlı sayıda değerle çalışıyor olabilirsiniz:
- Eğer 5 eleman gibi bir şeyi sıralıyorsanız, hızlı O(N log(N)) quicksort kullanmak istemezsiniz; küçük girdiler üzerinde iyi performans gösteren insertion sort kullanmak istersiniz. Bu tür durumlar genellikle böl ve yönet algoritmalarında ortaya çıkar; burada problemi özyinelemeli sıralama, hızlı Fourier dönüşümleri veya matris çarpımı gibi daha küçük alt problemlere bölersiniz.
- Bazı gizli gerçekler nedeniyle bazı değerler etkin bir şekilde sınırlandırılmışsa (örneğin, ortalama insan adı belki 40 harfle yumuşak bir şekilde sınırlandırılmıştır ve insan yaşı yaklaşık 150 ile yumuşak bir şekilde sınırlandırılmıştır). Terimleri etkin bir şekilde sabit hale getirmek için girdinize sınırlar da koyabilirsiniz.
Pratikte, aynı veya benzer asimptotik performansa sahip algoritmalar arasında bile, göreceli değerleri aslında başka şeyler tarafından yönlendirilebilir, örneğin: diğer performans faktörleri (quicksort ve mergesort’un her ikisi de O(N log(N)), ancak quicksort CPU önbelleklerinden yararlanır); uygulama kolaylığı gibi performans dışı hususlar; bir kütüphanenin mevcut olup olmadığı ve kütüphanenin ne kadar saygın ve bakımlı olduğu.
Programlar ayrıca 500MHz’lik bir bilgisayarda 2GHz’lik bir bilgisayara göre daha yavaş çalışacaktır. Bunu kaynak sınırlarının bir parçası olarak görmüyoruz, çünkü ölçeklendirmeyi gerçek saniye başına değil, makine kaynakları açısından (örneğin saat döngüsü başına) düşünüyoruz. Bununla birlikte, emülasyon altında çalışıp çalışmadığınız veya derleyicinin kodu optimize edip etmediği gibi performansı ‘gizlice’ etkileyebilecek benzer şeyler vardır. Bunlar bazı temel işlemlerin daha uzun sürmesine (birbirlerine göre bile), hatta bazı işlemlerin asimptotik olarak hızlanmasına ya da yavaşlamasına (birbirlerine göre bile) neden olabilir. Bu etki farklı uygulama ve/veya ortamlar arasında küçük ya da büyük olabilir. Bu küçük ekstra işi çıkarmak için dil veya makine değiştirir misiniz? Bu, performanstan daha önemli olabilecek yüzlerce başka nedene (gereklilik, beceriler, iş arkadaşları, programcı üretkenliği, zamanınızın parasal değeri, aşinalık, geçici çözümler, neden assembly veya GPU değil, vb…) bağlıdır.
Yukarıdaki konular, kullanılan programlama dili seçiminin etkisi gibi, neredeyse hiçbir zaman sabit faktörün bir parçası olarak düşünülmez (düşünülmemelidir de); yine de bunların farkında olunmalıdır çünkü bazen (nadiren de olsa) işleri etkileyebilirler. Örneğin cpython’da, yerel öncelik kuyruğu uygulaması asimptotik olarak optimal değildir (ekleme veya find-min seçiminiz için O(1) yerine O(log(N)); başka bir uygulama kullanıyor musunuz? Muhtemelen hayır, çünkü C uygulaması muhtemelen daha hızlıdır ve muhtemelen başka yerlerde de benzer sorunlar vardır. Bazı şeylerden ödün veririz; bunlar bazen önemlidirler, bazen de değildirler.