Algoritma analizi

Algoritma analizi veya diğer adıyla algoritma çözümlemesi, bilgisayar biliminde bir algoritmayı çalıştırabilmek için gereken kaynakların (zaman, yer gibi) miktarının tespitidir. Algoritmaların çoğunluğu, rastgele seçilmiş uzunluktaki girdiler ile çalışmak için tasarlanmıştır. Genellikle, bir algoritmanın verimlilik veya çalışma zamanı, adımların sayısı (zaman karmaşıklığı) veya depolama yerleri (alan karmaşıklığı)'nin girdi uzunluğuyla ilişkili olan işlev olarak ifade edilir.

Algoritma çözümlemesi, verilmiş olan hesaplamalı bir bilinmezi çözen herhangi bir algoritma aracılığıyla gereksinim duyulan kaynaklar için kuramsal tahminleri sağlayan hesaplamalı karmaşıklık kuramının önemli bir parçasıdır. O, verimli algoritmaları bulabilmek veya kıyaslayabilmek için bir anlayış geliştirmemizi sağlar.

Algoritmaların kuramsal çözümlemesinde, sonuşmazsal (asimptotik) anlamda onların karmaşıklığını tahmin etmektir, yani büyük miktarda ve rastsal olan girdiler için karmaşıklık işlevini tahmin etmektir. Büyük O gösterimi, Büyük omega gösterimi ve Büyük theta gösterimi, sonuşmazsaldaki sonları belirtmek için kullanılır. Mesela, ikili arama, aranmakta olan bir listenin uzunluğunun logaritmasına oranlı olan adım sayısında veya O(Log(n))'de veya konuşma diliyle "logaritmik zaman"da çalıştırmak için söylenilir. Genellikle sonuşmazsal tahminler kullanılır, çünkü aynı algoritmanın farklı gerçekleştirmeleri, verimlik açısından diğer algoritmalara kıyasla farklı olabilir. Bunlara rağmen verilen bir algoritmanın herhangi iki "akla yatkın" gerçekleştirmesinin verimliliği, saklı sabit adı verilen bir çarpımsal sabit unsuru aracılığıyla ilişkilidir.

Verimliliği kesin olan yani sonuşmazsal olmayan ölçümler, bazen hesaplanılmış olur, ancak genellikle hesaplama taslamı (modeli) kullanılarak çağrılan algoritmanın belirli gerçeklemesini dikkate alan belirli varsayımlara gereksinim duyarlar. Bir hesaplama taslamı, soyut bilgisayar açısından tanımlanılabilinir. Mesela, Turing makinesi, ve/veya birim zamanda yürütülen belirli işlemlerin olduğu esaslar tarafından. Örnek için, n adet elemanı olan ikili aramayı uyguladığımız sıralanmış dizi ve birim zamanda yapılmış olan dizideki elemanların her birine uğranmasını garanti edersek, o zaman en fazla log₂ n + 1 zaman birimi, bir cevabın döndürülmesi için yeterlidir.