Asimptotik Analiz
Asimptotik analiz, bir algoritmanın çalışma süresinin veya bellek kullanımının girdi boyutu büyüdükçe nasıl arttığını tanımlar; bu analiz, büyüme oranını sabitleri ve düşük dereceli terimleri göz ardı ederek yakalamak için büyük-O, büyük-Omega ve büyük-Theta gibi gösterimleri kullanır.
Tanım
Asimptotik analiz, bir fonksiyonun argümanı sonsuza yaklaştığında büyüme oranının karakterize edilmesidir; algoritma analizinde ise, sabit faktörleri ve düşük dereceli terimleri bastıran sıra gösterimini kullanarak zaman veya alan kullanımının girdi boyutuyla nasıl ölçeklendiğini ifade eder.
Kapsam
Bu konu, kaynak kullanımını karakterize etmek için kullanılan asimptotik gösterimleri — büyük-O (üst sınır), büyük-Omega (alt sınır), büyük-Theta (sıkı sınır) ve katı küçük-o ile küçük-omega — standart büyüme sınıfları (sabit, logaritmik, doğrusal, doğrusal-logaritmik, polinom, üstel) ve bu sınırları manipüle etme kuralları ile birlikte ele almaktadır. Sabit faktörlerin ve düşük dereceli terimlerin neden soyutlandığını ve asimptotik karşılaştırmaların ölçekleme davranışını nasıl öngördüğünü inceler. Bu sınırları elde etmek için kullanılan ve ayrı olarak ele alınan tekrarlama çözme mekanizmalarını kapsamaz.
Temel sorular
- Büyük-O, büyük-Omega ve büyük-Theta, bir fonksiyonun büyümesi hakkında neyi iddia etmektedir?
- Asimptotik karşılaştırmada sabit faktörler ve düşük dereceli terimler neden göz ardı edilmektedir?
- Yaygın büyüme sınıfları en yavaştan en hızlı büyüyene doğru nasıl sıralanmaktadır?
- Asimptotik sınırlar, bir algoritmanın büyük girdilere nasıl ölçekleneceğini nasıl öngörmektedir?
- Asimptotik olarak daha yavaş algoritmalar pratikte ne zaman hala tercih edilebilir olabilmektedir?
Anahtar kavramlar
- büyük-O gösterimi
- büyük-Omega gösterimi
- büyük-Theta gösterimi
- küçük-o ve küçük-omega
- büyüme sınıfları
- sabit faktörler
- düşük dereceli terimler
- ölçeklenebilirlik
Temel kuramlar
- Sıra gösterimi
- Büyük-O bir fonksiyonu sabit bir faktör dahilinde yukarıdan sınırlar, büyük-Omega aşağıdan sınırlar ve büyük-Theta her iki yönden sınırlar; Knuth tarafından bilgisayar bilimi için standartlaştırılan bu tanımlar, büyüme oranları için kesin bir dil sağlamaktadır.
- Büyüme oranlarının baskınlığı
- Girdi boyutu büyüdükçe, yüksek dereceli terimler baskın hale gelir, bu nedenle bir algoritmanın asimptotik sınıfı (örneğin doğrusal-logaritmik ve karesel) sabit faktörlerden bağımsız olarak nihayetinde ölçeklenebilirliğini belirlemektedir.
Klinik önem
Asimptotik gösterim, algoritma verimliliğini tartışmak için ortak dildir: mühendislerin aday algoritmaları karşılaştırmasına, bir sistemin daha büyük iş yüklerine ölçeklenip ölçeklenmeyeceğini tahmin etmesine ve dokümantasyonlarda, mülakatlarda, kütüphane ve standartların analizinde performans garantilerini iletmesine olanak tanır.
Tarihçe
Büyük-O ve ilgili gösterimler, 19. yüzyıl analitik sayı teorisinde Bachmann ve Landau ile ortaya çıkmıştır (bu nedenle 'Landau gösterimi' olarak da bilinir). Donald Knuth, 1960'lı ve 1970'li yıllarda bunları algoritmaların analizi için uyarlamış ve standartlaştırmıştır; buna bilgisayar bilimlerinde büyük-Omega ve büyük-Theta kullanımını açıklayan 1976 tarihli bir not da dahildir.
Öne çıkan isimler
- Donald Knuth
- Paul Bachmann
- Edmund Landau
İlgili konular
Temel eserler
- knuth1976bigo
- cormen2009
Sıkça sorulan sorular
- Daha küçük bir büyük-O her zaman daha hızlı bir algoritma anlamına mı gelmektedir?
- Belirli bir girdi boyutu için her zaman böyle olmayabilir. Büyük-O, girdi boyutu sonsuza yaklaştıkça büyümeyi tanımlar ve sabit faktörleri gizler, bu nedenle asimptotik sınıfı daha kötü olan bir algoritma küçük girdilerde daha hızlı olabilmektedir. Büyük girdiler ve ölçeklenebilirlik için daha iyi bir rehberdir.
- Büyük-O ve büyük-Theta arasındaki fark nedir?
- Büyük-O yalnızca büyüme üzerinde bir üst sınır verir, bu nedenle algoritmanın belirli bir orandan daha kötü olmadığını belirtir. Büyük-Theta ise sıkı bir sınır verir ve büyümenin hem yukarıdan hem de aşağıdan bu oranla eşleştiğini iddia eder. Bir algoritmanın Theta(n log n) olduğunu söylemek, O(n log n) ifadesinden daha güçlü ve daha kesin bir ifadedir.