Mathematical Analysis of Nonrecursive Algorithms

Kategori: Algorithm Design and Analysis , 05 Haziran 2020 , JanFranco


Bu bölümde örneklerle algoritmanın efektifliğini ölçeceğiz. Aşağıdaki algoritma ile başlayalım:


Algorithm MaxElement(A[0..n-1])

maxval <- A[0]
for i <- 1 to n - 1 do
    if A[i] > maxval
	maxval <- A[i]
return maxval
Bir dizideki en büyük elemanı bulan basit bir algoritmanın pseudocode'unu görüyoruz. Aşağıdaki adımları izleyelim:

1- Girdi büyüklüğünü belirleyelim:

Burada girdi büyüklüğü dizinin eleman sayısıdır. Burada eleman sayımız n'dir.

2- Algoritmanın temel operasyonunu bulalım:

Burada temel operasyon algoritmayla bağdaştırılabilir olmalıdır. Karşılaştırma işlemini seçelim.

3- Temel operasyonun kaç kez yapıldığını bulalım:

Temel operasyon her adımda 1 kez yapılıyor. Girdi büyüklüğümüz n olduğuna göre temel operasyon n kez yapılacak.

4- Toplam sembolünde yazalım:

C(n) = Sum(i=1 to n-1) 1.

5- Hesaplayalım:

C(n) = n-1-1+1 = n-1

6- Sonuç:

Bu durumda bu algoritmayı O(n) sınıfına dahil edebiliriz. Bir örnek daha yapalım:


Algorithm UniqueElements(A[0..n-1])

for i <- 0 to n - 2 do
    for j <- i + 1 to n - 1 do
	if A[i] = A[j]
	    return false
return true
Burada bir dizideki elemanların unique yani eşsiz olup olmadığını kontrol eden bir algoritmanın sahte kodunu görüyoruz. Girdi büyüklüğümüz eleman sayısıdır. Yani n olacak. Temel operasyonumuz eşitlik karşılaştırmasıdır ve bu operasyon ikinci for döngüsündedir. Bu operasyonun kaç kez çalıştığını hesaplayalım:

C(n) = sum(i=0 to n-2) sum(j=i+1 to n-1) 1 = sum(i=0 to n-2) n - 1 - i = (n-1)n / 2

Bu durumda bu algoritmayı O(n^2) sınıfına dahil edebiliriz. Son bir örnek daha yapalım:


Algorithm Binary(n)

count <- 1
while n > 1 do
    count <- count + 1
    n <- n / 2
return count
Bu algoritma bir sayının binary gösterimindeki rakam sayısını buluyor. Girdi büyüklüğümüz sayının kendisi yani n. Temel operasyon burada count++ da olabilir n <- n/2 de olabilir. İki operasyon da aynı döngüde, ikisi de aynı sayıda çalıştırılacak. Bu nedenle hangisini seçtiğimizin bir önemi yok. count++ operasyonunu seçelim. Her adımda n sayısını ikiye bölüyoruz. Bu nedenle operasyonun toplam çalışma sayısı log(2)n + 1 olur. Bu durumda da bu algoritmayı O(log n) sınıfına dahil edebiliriz.


Sonraki Yazı: Mathematical Analysis of Recursive Algorithms
Yorumlar

Henüz bir yorum bulunmuyor.