Algoritmaların Karmaşıklığı ve Analizi
Algoritmaların analizi, bir algoritmanın çalışma süresinin ve bellek kullanımının girdi boyutuyla nasıl arttığını nicel olarak belirlemekte; algoritmaları karşılaştırmak ve doğası gereği zor olan problemleri tanımlamak için kullanılan asemptotik terminoloji ve araçları sağlamaktadır.
Tanım
Algoritmaların analizi, bir algoritmanın girdi boyutunun bir fonksiyonu olarak tükettiği hesaplama kaynaklarının — başlıca zaman ve alan — incelenmesidir; bu kaynak sınırlarını türetmek, ifade etmek ve karşılaştırmak için kullanılan tekniklerle birlikte ele alınmaktadır.
Kapsam
Bu alan, algoritmik kaynak kullanımının ölçümünü ve karşılaştırılmasını kapsamaktadır: asemptotik gösterim (big-O, big-Omega, big-Theta), özyinelemeli algoritmalardan kaynaklanan tekrarların çözümü, işlem dizilerinin amortize edilmiş analizi ve algoritma tasarımına uygulandığı şekliyle hesaplama karmaşıklığı sınıflarının ve NP-tamlığının temelleri. En kötü durum, ortalama durum ve amortize edilmiş maliyet ile çözülebilir (tractable) ve çözülemez (intractable) problemler arasındaki ayrımı ele almaktadır. Daha geniş hesaplama kuramı (hesaplanabilirlik, biçimsel karmaşıklık sınıfları) ayrı bir alt alana ait olup, burada somut algoritmaların analizine odaklanılmaktadır.
Alt konular
Temel sorular
- Bir algoritmanın kaynak kullanımı, makine ve uygulama detaylarından bağımsız olarak nasıl ifade edilmektedir?
- En kötü durum, ortalama durum ve amortize edilmiş analizler bize ayrı ayrı ne anlatmaktadır?
- Özyinelemeli algoritmalar tarafından üretilen tekrarlar, asimptotik sınırlar için nasıl çözülmektedir?
- Hiçbir algoritmanın daha iyisini yapamayacağını gösteren alt sınırlar nasıl belirlenebilmektedir?
- Bir problemin NP-tam olması ne anlama gelmektedir ve tasarım için neden önemlidir?
Anahtar kavramlar
- big-O, big-Omega, big-Theta
- en kötü durum ve ortalama durum analizi
- tekrarlama bağıntıları
- master theorem
- amortize edilmiş analiz
- alt sınırlar
- polinom zamanı
- NP-completeness
Temel kuramlar
- Asymptotik gösterim
- Big-O, big-Omega ve big-Theta, girdi boyutu arttıkça kaynak kullanımının büyüme oranını tanımlamakta, sabitleri ve düşük dereceli terimleri soyutlayarak algoritmaların makineden bağımsız karşılaştırılmasını sağlamaktadır.
- Çözülebilirlik (Tractability) ve NP-tamlığı
- Polinom zamanda çözülebilen problemler çözülebilir (tractable) kabul edilmektedir; NP-tam problemler, NP'deki tüm problemlerin indirgenebildiği problemlerdir ve herhangi biri için bir polinom algoritması bulmak hepsini çözecektir, bu soru (P versus NP) hala açıktır.
Klinik önem
Algoritmaların analizi, hangi algoritmanın veya veri yapısının kullanılacağına dair her mühendislik kararına rehberlik etmekte, veri büyüdükçe sistemlerin nasıl ölçekleneceğini tahmin etmektedir. Bir problemin NP-zor olduğunu fark etmek, uygulayıcılara kesin bir polinom algoritması yerine yaklaştırma, sezgisel veya özel durum yöntemleri aramalarını söylemekte; optimizasyon, çizelgeleme ve büyük ölçekli hesaplama alanlarındaki çalışmaları şekillendirmektedir.
Tarihçe
Asymptotik gösterim, analitik sayı teorisinden bilgisayar bilimine aktarılmış ve 1960'lı ve 1970'li yıllarda Donald Knuth tarafından popülerleştirilmiştir. NP-tamlığı kuramı Stephen Cook (1971) tarafından kurulmuş ve Richard Karp (1972) tarafından genişletilerek, çözülebilir ve çözülemez problemler arasındaki sınır etrafında algoritma tasarımını yeniden şekillendirmiştir.
Tartışmalar
- P versus NP
- Çözümleri hızlı bir şekilde doğrulanabilen her problemin hızlı bir şekilde çözülüp çözülemeyeceği (P = NP), teorik bilgisayar biliminin merkezi açık sorusudur; P'nin NP'ye eşit olmadığı yaygın olarak varsayılmaktadır, ancak henüz bir kanıtı bulunmamaktadır.
Öne çıkan isimler
- Donald Knuth
- Stephen Cook
- Richard Karp
- Robert Tarjan
İlgili konular
Temel eserler
- cormen2009
- knuth1976bigo
- kleinberg2006
Sıkça sorulan sorular
- En kötü durum ve ortalama durum analizi arasındaki fark nedir?
- En kötü durum analizi, her boyut için en elverişsiz girdideki kaynak kullanımını sınırlayarak bir garanti sunmaktadır. Ortalama durum analizi ise, girdi dağılımı üzerinden beklenen kaynak kullanımını tahmin etmektedir; bu, tipik performansı daha iyi temsil edebilmekle birlikte, girdi dağılımı hakkındaki varsayımlara bağlıdır.
- Bir problem NP-tam ise, çözülmesi umutsuz mudur?
- Hayır. NP-tamlığı, en kötü durum için verimli bir algoritma bilinmediği anlamına gelmektedir, ancak örnekler genellikle yaklaştırma algoritmaları, sezgisel yöntemler, pratikte yeterince hızlı olan üstel algoritmalar veya özel yapıdan yararlanılarak çözülebilmektedir. Bu, imkansızlık değil, bir strateji değişikliğinin işaretidir.