Python - Algoritma Analizi

Algoritma Analizi

Bir algoritmanın etkinliği, uygulama öncesinde ve sonrasında olmak üzere iki farklı aşamada analiz edilebilir. Aşağıdakilerdir -

A Priori Analysis- Bu, bir algoritmanın teorik analizidir. Bir algoritmanın verimliliği, diğer tüm faktörlerin, örneğin işlemci hızının sabit olduğu ve uygulama üzerinde hiçbir etkisinin olmadığı varsayılarak ölçülür.
A Posterior Analysis- Bu, bir algoritmanın deneysel bir analizidir. Seçilen algoritma, programlama dili kullanılarak uygulanır. Bu daha sonra hedef bilgisayar makinesinde yürütülür. Bu analizde, çalışma süresi ve gerekli alan gibi gerçek istatistikler toplanır.

Algoritma Karmaşıklığı

Varsayalım X bir algoritmadır ve n Girdi verilerinin boyutu, X algoritması tarafından kullanılan zaman ve alan, X'in verimliliğini belirleyen iki ana faktördür.

Time Factor - Zaman, sıralama algoritmasındaki karşılaştırmalar gibi anahtar işlemlerin sayısı sayılarak ölçülür.
Space Factor - Alan, algoritmanın gerektirdiği maksimum bellek alanı sayılarak ölçülür.

Bir algoritmanın karmaşıklığı f(n) algoritmanın ihtiyaç duyduğu çalışma süresini ve / veya depolama alanını verir. n giriş verilerinin boyutu olarak.

Uzay Karmaşıklığı

Bir algoritmanın uzay karmaşıklığı, algoritmanın yaşam döngüsü boyunca ihtiyaç duyduğu bellek alanı miktarını temsil eder. Bir algoritmanın gerektirdiği alan, aşağıdaki iki bileşenin toplamına eşittir -

Sorunun boyutundan bağımsız, belirli verileri ve değişkenleri depolamak için gereken alan olan sabit bir parça. Örneğin, kullanılan basit değişkenler ve sabitler, program boyutu vb.
Değişken parça, boyutu problemin boyutuna bağlı olan değişkenler tarafından ihtiyaç duyulan bir alandır. Örneğin, dinamik bellek ayırma, özyineleme yığın alanı vb.

Herhangi bir P algoritmasının uzay karmaşıklığı S (P), S (P) = C + SP (I) 'dir, burada C sabit kısımdır ve S (I), örnek karakteristiğine I bağlı olan algoritmanın değişken kısmıdır. kavramı açıklamaya çalışan basit bir örnektir -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Burada A, B ve C olmak üzere üç değişkenimiz ve bir sabitimiz var. Dolayısıyla S (P) = 1 + 3. Uzay, verilen değişkenlerin veri türlerine ve sabit türlere bağlıdır ve buna göre çarpılacaktır.

Zaman Karmaşıklığı

Bir algoritmanın zaman karmaşıklığı, algoritmanın tamamlanana kadar çalışması için gereken süreyi temsil eder. Zaman gereksinimleri sayısal bir fonksiyon T (n) olarak tanımlanabilir, burada T (n) her adımın sabit zaman tüketmesi koşuluyla adım sayısı olarak ölçülebilir.

Örneğin, iki n-bit tamsayının eklenmesi, nadımlar. Sonuç olarak, toplam hesaplama süresi T (n) = c ∗ n'dir, burada c, iki bitin eklenmesi için geçen süredir. Burada, girdi boyutu arttıkça T (n) 'nin doğrusal olarak büyüdüğünü gözlemliyoruz.