Varsayalım iki algoritma var:

for (int i = 0; i < n; i  ) {
  for (int j = 0; j < n; j  ) {
    //do something in constant time
  }
}

Bu da doğal olarak O(n^2). Ben de varsayalım:

for (int i = 0; i < 100; i  ) {
  for (int j = 0; j < n; j  ) {
    //do something in constant time
  }
}

Bu O(n) O(n) O(n) O(n) ... O(n) = O(n)

Benim ikinci algoritma olsa bile O(n), daha uzun sürecek gibi görünüyor. Birisi bu genişletebilirsiniz? Konuyu açayım çünkü ben sık sık görmek algoritmaları nerede olacak, örneğin, gerçekleştirmek bir sıralama ilk adım gibi bir şey bu, ve zaman belirleme toplam karmaşıklığı, sadece en karmaşık öğesi olan sınır algoritması.

Aslında büyük-O sadece bir üst sınır O(1) bir algoritma (ya da gerçekten herhangi bir algoritma O(n2) veya daha az zaman alıyor) O(n2) alır diyorsun yani. Bu amaçla, sadece sıkı bağlı olan büyük Teta (Θ) gösterim, geçin. Daha fazla bilgi için the formal definitions bkz.

Eğer sadece büyük-O biliyor (yanlış) büyük-O bir sıkı bağlı olduğunu öğretti oldum olası. Eğer öyleyse, muhtemelen sadece büyük-O demek öğrendin ne büyük Teta kabul edebilirsiniz.

Ben, aynen bu cevap, kabul soruldu (veya demek) büyük-Teta değil, büyük-O. Değilse, az önce bahsettiğimiz, eğer konuşmak hakkında büyük-O, bunun yerine bir "anything goes" durum - O(n) biri olabilir daha hızlı, O(n2) Bir daha hızlı olabilir ya da onlar-ebilmek almak aynı miktarda zaman (asimptotik) - genellikle yapamam özellikle anlamlı sonuçlar bakımındankarşılaştırmaalgoritmalar big-O, yalnızca o, bu algoritma bu sürenin daha uzun (asimptotik olarak) kabul etmiyor bazı algoritma big-O, verdiği söylenebilir.

Asimptotik karmaşıklığı (ne de büyük O ve büyük Teta temsil eder) tamamen yok sayıyor sabit etkenler - sadece amaçlanan ver bir göstergesi ne kadar süre değişecek gibi boyutu büyük giriş alır.

Yani bu kesinlikle olası bir Θ(n) algoritma alabilir daha uzun bir Θ(n2) için verilen n - n bu olacak için olacak gerçekten bağlı algoritmaları dahil - için spesifik bir örnek, bu dava için n < 100 görmezden olasılığı iyileştirmeleri farklı ikisinin arasında.

Herhangi iki algoritmaları görmek olasıdır ne sırasıyla, Θ(n) Θ(n2) zaman ayırdığınız için:

• Θ(n) algoritma n küçük olduğunda daha yavaş, daha sonra Θ(n2) n arttıkça daha yavaş olur
  eğer Θ(n) bir daha karmaşık olur (yani daha yüksek sabit faktörler vardır ya
• Θ(n2) her zaman daha yavaştır.

Kesinlikle olsa damümkünbu Θ(n) algoritma olabilir yavaş, sonra Θ(n2) bir sonra Θ(n) bir daha, n artırır kadar n alır çok büyük, hangi noktadan itibaren Θ(n2) kimse her zaman daha yavaş, ancak bu büyük ihtimal olur.

Biraz daha matematiksel terimlerden için:

Hadi Θ(n2) algoritma c bazı cn2 operasyon gerekir.

Θ(n) algoritma d bazı dn operasyonlar sürüyor.

Bu hat ile the formal definition beri düşünebiliriz bu tutar için n 0'dan yüksek (yani tüm n) ve bu iki işlev arasında olan süre yatıyor aynıdır.

Satır ile bir olduğunuzu söylemek c = 1 d = 100 Θ(n) algoritma olurdu yavaş kadar n = 100, bu noktada, Θ(n2) algoritma olacağını daha yavaş.

(WolframAlpha nezaket).