Algoritma Karmaşıklığı Örnekleri 1

Bir şeyi en iyi öğrenmenin yolu örnek üzerinde çözüm yapmaktır. Biz de sizler için algoritma karmaşıklığının nasıl hesaplandığını direkt kod üzerinde gösterelim dedik. Burada satır satır yaklaşımda bulunduğumuza dikkat etmeniz lazım. Algoritma karmaşıklığı örnekleri üzerinden konunun büyük bir bölümü anlamanız mümkündür.

Algoritma Karmaşıklık problemi 1: Aşağıdaki kodların zaman karmaşıklığını bulunuz.
  1. int[][] a = new int[N][N]; /* NxN matrix
  2. for i from 0 to N {
  3. for j from 0 to N {
  4. a[i][j] = i + j
  5. }
  6. }
Yukarıdaki koda bakalım. Eğer big O notasyonunu hesaplayacaksak for döngülerine bakmamız yeterli. İçiçe for döngüleri daima N^2 döner. O(n^2) 

 Algoritma Karmaşıklık problemi 2:  Aşağıdaki kodların zaman karmaşıklığını bulunuz.
  1. for i from 0 to n {
  2. print i /* line 2 */
  3. }

 Gayet basit bir for döngüsü var. N kez döneceği için O(n) olacaktır.

Algoritma Karmaşıklık problemi 3: Aşağıdaki kodların zaman karmaşıklığını bulunuz.


  1. for i from 0 to A.length {
  2. int j = 0;
  3. while (a[i] != b[j]) {
  4. print a[i]
  5. j = j + 1
  6. }
  7. }
Bu kez işin içine While döngüsü giriyor. Aslında burada bazı şeyler net olmadığından net hesaplama yapamayız. Ancak yaklaşık olarak O(a*b) diyebiliriz. Eğer b değerinin çok büyük olması mümkünse O(b) demek de mümkündür.


Algoritma Karmaşıklık problemi 4: Aşağıdaki kodların zaman karmaşıklığını bulunuz.

  1. int i = N;
  2. while i >= 1 {
  3. print i
  4. i = i / 2
  5. }

son sorumuz biraz zor olsun istedim. Aslında while döngüsünü görünce N deyip geçerdik değil mi? Ancak kazın ayağı öyle değil. Çünkü while döngüsü içerisindeki i değeri maniple edilmiş. Her döngüde i değeri yarıya indiriliyor. Bunu gördük mü aklımıza logaritmik bir değer gelmesi lazım. Aslında biraz ezberci olacak ama, işlem yarılanıyorsa O(logn) dememiz lazım. Ancak illa işlem üzerinden görmek istiyoruz derseniz aşağıya bakalım.

2^x = n dersek x'i çözmek için iki tarafında logaritmasını almamız gerekiyor.
log(2^x) = logn
xlog(2) = log(n)
x = logn/log2

buradaki işlem bize x değerinin logn olduğunu gösteriyor.

Etiketler: , ,