En iyi, en kötü ve ortalama durum - Best, worst and average case
Gelen bilgisayar bilimleri , iyi , kötü ve ortalama vakalar belirli bir bölgesinin algoritma şeyi ifade kaynak kullanımıdır en azından , en fazla ve ortalama sırasıyla. Genellikle dikkate alınan kaynak çalışma süresidir, yani zaman karmaşıklığıdır , ancak bellek veya başka bir kaynak da olabilir. En iyi durum, n elemanın giriş verileri üzerinde minimum sayıda adımı gerçekleştiren fonksiyondur. En kötü durum, n boyutundaki girdi verileri üzerinde maksimum sayıda adım gerçekleştiren fonksiyondur. Ortalama durum, n elemanın giriş verileri üzerinde ortalama sayıda adım gerçekleştiren fonksiyondur.
In gerçek zamanlı bilgi işlem , en kötü durum yürütme süresi önemlidir gerekebilir ne kadar zaman bilmek beri sık sık özellikle kaygı vericidir en kötü durumda algoritma hep zamanında bitireceğini garantiye.
Ortalama performans ve en kötü durum performansı , algoritma analizinde en çok kullanılanlardır. Daha az yaygın olarak bulunan en iyi durum performansıdır , ancak kullanımları vardır: örneğin, bireysel görevlerin en iyi durumlarının bilindiği yerlerde, bunlar genel bir en kötü durum analizinin doğruluğunu artırmak için kullanılabilir. Bilgisayar bilimcileri , beklenen çalışma sürelerini belirlemek için olasılıksal analiz tekniklerini, özellikle de beklenen değeri kullanır.
Terimler başka bağlamlarda kullanılır; örneğin, bir elektronik devre elemanının maruz kaldığı salgın, en kötü durum sıcaklığının en kötü ve en iyi sonucu, vb. Belirtilen tolerans bileşenlerinin kullanıldığı durumlarda, cihazlar en kötü durum kombinasyonu ile düzgün çalışacak şekilde tasarlanmalıdır. toleranslar ve dış koşullar.
Algoritma için en iyi durum performansı
En iyi durum performansı terimi, bilgisayar bilimlerinde bir algoritmanın optimal koşullar altındaki davranışını tanımlamak için kullanılır. Örneğin, bir listede basit bir doğrusal arama için en iyi durum, istenen öğe listenin ilk öğesi olduğunda ortaya çıkar.
Algoritma geliştirme ve seçimi nadiren en iyi durum performansına dayanır: çoğu akademik ve ticari kuruluş, Ortalama durum karmaşıklığını ve en kötü durum performansını iyileştirmeyle daha fazla ilgilenir . Algoritmalar, sonlu bir girdi kümesine sabit kodlama çözümleri ile en iyi durumda iyi çalışma süresine sahip olacak şekilde önemsiz bir şekilde değiştirilebilir, bu da ölçümü neredeyse anlamsız hale getirir.
En kötü durum ve ortalama durum performansı
En kötü durum performans analizi ve ortalama durum performans analizi bazı benzerliklere sahiptir, ancak pratikte genellikle farklı araçlar ve yaklaşımlar gerektirir.
Tipik girdinin ne anlama geldiğini belirlemek zordur ve genellikle bu ortalama girdinin matematiksel olarak karakterize edilmesini zorlaştıran özellikleri vardır (örneğin, metin dizileri üzerinde çalışmak üzere tasarlanmış algoritmaları düşünün ). Benzer şekilde, belirli bir "ortalama durumun" (muhtemelen yalnızca algoritmanın bazı kullanımları için geçerli olacak) mantıklı bir açıklaması mümkün olduğunda bile, denklemlerin daha zor analiziyle sonuçlanma eğilimindedirler.
En kötü durum analizi, güvenli bir analiz sağlar (en kötü durum asla hafife alınmaz), ancak bu kadar çok adımı atacak (gerçekçi) bir girdi olmayabileceğinden aşırı karamsar olabilen bir analiz .
Bazı durumlarda güvenliği garanti altına almak için karamsar bir analiz kullanmak gerekebilir. Ancak çoğu zaman kötümser bir analiz fazla karamsar olabilir, bu nedenle gerçek değere yaklaşan ancak iyimser olabilen (belki de bazı bilinen düşük başarısızlık olasılığı olan) bir analiz çok daha pratik bir yaklaşım olabilir. Akademik teoride en kötü durum ve ortalama durum analizi arasındaki boşluğu kapatmak için modern bir yaklaşıma düzleştirilmiş analiz denir .
Tamamlanması genellikle küçük bir zaman alan, ancak periyodik olarak çok daha fazla zaman gerektiren algoritmaları analiz ederken, bir (muhtemelen sonsuz) bir dizi işlem üzerinde en kötü durum çalıştırma süresini belirlemek için amortize edilmiş analiz kullanılabilir . Bu itfa edilmiş en kötü durum maliyeti, ortalama durum maliyetine çok daha yakın olabilirken, yine de çalışma süresinde garantili bir üst sınır sağlar.
En kötü durum analizi, en kötü durum karmaşıklığı ile ilgilidir .
pratik sonuçlar
En kötü durum performansına sahip birçok algoritma, iyi bir ortalama durum performansına sahiptir. Çözmek istediğimiz problemler için bu iyi bir şey: Önem verdiğimiz belirli örneklerin ortalama olduğunu umabiliriz. İçin kriptografi , bu çok kötü: Biz bir şifreleme sorunun tipik örnekleri sert olmak istiyorum. Burada , en kötü durumun ortalama durumdan daha zor olmadığını veya eşdeğer olarak, ortalama durumun en kötü durumdan daha kolay olmadığını göstermek için bazı özel problemler için rastgele kendi kendine indirgenebilirlik gibi yöntemler kullanılabilir.
Öte yandan, hash tabloları gibi bazı veri yapıları çok kötü en kötü durum davranışlarına sahiptir, ancak yeterli büyüklükte iyi yazılmış bir hash tablosu istatistiksel olarak hiçbir zaman en kötü durumu vermeyecektir; gerçekleştirilen ortalama işlem sayısı üstel bir azalma eğrisini takip eder ve bu nedenle bir işlemin çalışma süresi istatistiksel olarak sınırlandırılır.
Örnekler
Sıralama algoritmaları
| algoritma | Veri yapısı | Zaman karmaşıklığı: En iyi | Zaman karmaşıklığı:Ortalama | Zaman karmaşıklığı: En kötü | Uzay karmaşıklığı:En kötü |
|---|---|---|---|---|---|
| Hızlı sıralama | Dizi | O( n günlüğü( n )) | O( n günlüğü( n )) | O( n 2 ) | O( n ) |
| Sıralamayı birleştir | Dizi | O( n günlüğü( n )) | O( n günlüğü( n )) | O( n günlüğü( n )) | O( n ) |
| yığın sıralama | Dizi | O( n günlüğü( n )) | O( n günlüğü( n )) | O( n günlüğü( n )) | O(1) |
| Düzgün sıralama | Dizi | O( n ) | O( n günlüğü( n )) | O( n günlüğü( n )) | O(1) |
| Kabarcık sıralama | Dizi | O( n ) | O( n 2 ) | O( n 2 ) | O(1) |
| Ekleme sıralama | Dizi | O( n ) | O( n 2 ) | O( n 2 ) | O(1) |
| Seçim sıralaması | Dizi | O( n 2 ) | O( n 2 ) | O( n 2 ) | O(1) |
| bogo sıralama | Dizi | O( n ) | O( n n !) | O(∞) | O(1) |
- Tamamen farklı ve başlangıçta rastgele sırada olduğu varsayılan n öğeden oluşan bir listeye uygulanan ekleme sıralama . Ortalama olarak, A 1 ... A j listesindeki öğelerin yarısı, A j +1 öğesinden daha küçüktür ve yarısı daha büyüktür. Bu nedenle, algoritma ortalamaya eklenecek ( j + 1)'inci öğeyi önceden sıralanmış alt listenin yarısı ile karşılaştırır, böylece t j = j /2 olur. Ortaya çıkan ortalama durum çalışma süresi, en kötü durum çalışma süresi gibi, girdi boyutunun ikinci dereceden bir işlevini verir.
- Quicksort , n öğeden oluşan bir listeye uygulandı , yine hepsinin farklı olduğu ve başlangıçta rastgele sırada olduğu varsayıldı. Bu popüler sıralama algoritması , pratikte çok hızlı bir algoritma olmasına katkıda bulunan O( n log( n )) ortalama durum performansına sahiptir . Ancak en kötü durum girdisi verildiğinde performansı O( n 2 ) değerine düşer . Ayrıca, "en kısa ilk" ilkesiyle uygulandığında, en kötü durum alanı karmaşıklığı bunun yerine O(log( n ) ile sınırlandırılır ).
- Heapsort, tüm öğeler aynı olduğunda O(n) zamanına sahiptir. Heapify, O(n) zaman alır ve ardından öğeleri öbekten çıkarmak, n öğelerin her biri için O(1) zamanıdır. Tüm öğelerin farklı olması gerekiyorsa, çalışma süresi O(nlog(n)) olur.
- Öğeler ilk yinelemede sıralandığında Bogosort'un O(n) süresi vardır. Her yinelemede, tüm öğeler sırayla kontrol edilir. n var! olası permütasyonlar; dengeli bir rasgele sayı üreteci ile dizinin hemen hemen her permütasyonu n! yinelemeler. Bilgisayarların hafızası sınırlıdır, bu nedenle üretilen sayılar döngü halindedir; her permütasyona ulaşmak mümkün olmayabilir. En kötü durumda bu, sonsuz bir döngü olan O(∞) zamanına yol açar.
Veri yapıları
| Veri yapısı | Zaman karmaşıklığı | Uzay karmaşıklığı | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Ort: Dizine Ekleme | Ort: Arama | Ort: Ekleme | Ort: Silme | En Kötü: İndeksleme | En Kötü: Arama | En Kötü: Ekleme | En Kötü: Silme | En kötüsü | |
| Temel dizi | O(1) | O( n ) | O( n ) | O( n ) | O(1) | O( n ) | - | - | O( n ) |
| dinamik dizi | O(1) | O( n ) | O( n ) | - | O(1) | O( n ) | O( n ) | - | O( n ) |
| Tek başına bağlantılı liste | O( n ) | O( n ) | O(1) | O(1) | O( n ) | O( n ) | O(1) | O(1) | O( n ) |
| Çift bağlantılı liste | O( n ) | O( n ) | O(1) | O(1) | O( n ) | O( n ) | O(1) | O(1) | O( n ) |
| karma tablo | - | O(1) | O(1) | O(1) | - | O( n ) | O( n ) | O( n ) | O( n ) |
| İkili arama ağacı | - | O(günlük ( n )) | O(günlük ( n )) | O(günlük ( n )) | - | O( n ) | O( n ) | O( n ) | O( n ) |
| B ağacı | - | O(günlük ( n )) | O(günlük ( n )) | O(günlük ( n )) | - | O(günlük ( n )) | O(günlük ( n )) | O(günlük ( n )) | O( n ) |
| Kırmızı-siyah ağaç | - | O(günlük ( n )) | O(günlük ( n )) | O(günlük ( n )) | - | O(günlük ( n )) | O(günlük ( n )) | O(günlük ( n )) | O( n ) |
| AVL ağacı | - | O(günlük ( n )) | O(günlük ( n )) | O(günlük ( n )) | - | O(günlük ( n )) | O(günlük ( n )) | O(günlük ( n )) | O( n ) |
- n elemanlı bir listede doğrusal arama . Mutlak en kötü durumda, arama her öğeyi bir kez ziyaret etmelidir. Bu, aranan değer listedeki son öğe olduğunda veya listede olmadığında olur. Ancak, ortalama olarak, aranan değerin listede olduğu ve her liste öğesinin aranan değer olma olasılığının eşit olduğu varsayılırsa, arama yalnızca n /2 öğesini ziyaret eder .
Ayrıca bakınız
- Sıralama algoritması - çeşitli algoritmaların çok sayıda performans analizinin olduğu bir alan.
- Arama veri yapısı – belirli öğelerin verimli bir şekilde alınmasını sağlayan herhangi bir veri yapısı
- En kötü durum devre analizi
- Düzleştirilmiş analiz
- Aralık sonlu eleman
- Büyük O gösterimi