5.2.2.1. Yürütme Zamanı ve Karmaşıklık Hesabı

Örnek: Aşağıda matris çarpa işlemi yapan bir fonksiyon görülmektedir; A ve B matrisleri giriş C ise sonucun saklandığı matristir. Fonksiyonun n.m boyutlu A matrisiyle n.r boyutlu B matrisini çarpıp n.r boyutlu C matrisini elde etmesi için gerekli T(n)'ni ve büyük O notasyonundaki karmaşıklığı hesaplayınız. Eğer matrisler n.n boyunda kare matrisler olsaydı T(n) ve O(?) ne olurlardı?

 void carpMatris(A, B, C)
float A[n][m], B[m][r], C[n][r];
{
   int x, y,z;
   for(x=0, x<n; x++) {
        for(z=0; z<r; z++) {
           aratoplam=0;
           for(y=0; y<m; y++)
                 aratoplam+=A[x][y]*B[y][z];
                       C[x][z]=aratoplam;
                }
      }
}

Çözüm: Burada üç tane döngü vardır ve sayaç değişkenleri x, y ve z olarak adlandırılmıştır; bağıntılar ise matrisin boyutunu belirleyen n, m ve r'ye bağlı çıkacaktır. Hesaplama yapılırken şöyle bir yol izlenebilir: önce for deyimlerinde yapılan işlem sayısı bulunur ve ardından her for döngüsü içerisinde yapılan işlem sayısı bulunur ve her ikisi toplanır. . satırda for deyiminde x=0 işlemi 1 kez; x<n işlemi (n+1) kez ve x++ işlemi n kez yapılır. Dolayısıyla, en dışdaki for deyimi içerisinde yapılan işlem sayısı 1+(n+1)+n= 2n+2 kez yapılır. . satırdaki for deyiminde ise, işlem sayısı (2r+2)n, . satırdaki for deyiminde ise (2m+2)nr çıkarak. Dolayısıyla, yalnızca for deyimleri için yapılan işlem sayısı Tfor(n, m, r)= (2n+2)+(2r+2)n+(2m+2)nr olur. Döngüler içerisindeki işlem sayısı ise, . satırdaki işlem sayısı nr kez; benzer şekilde . satırda da nr kez yapılır; . satırdaki işlem sayısı ise (satırın bütünü 1 işlem kabul edilerek) nmr olur. Tdöngü içi(n, m, r)= nr+nr+nmr olur. Buna göre toplam işlem sayısı T(n, m, r)= Tfor(n, m, r)+ Tdöngü içi(n, m, r) bağıntısı uyarınca,

T(n, m, r)= (2n+2)+(2r+2)n+(2m+2)nr+ nr+nr+nmr
             = 2n+2+2nr+2n+2mnr+2nr+nr+nr+nmr
             = 3nmr+6nr+4n+2

olarak bulunur. Yürütme zamanı bağıntısından O(?) karmaşıklığı, kabaca şöyle bulunur; tüm sabit çarpanlar ve düşük dereceli terimler atılır. Dolayısıyla karmaşıklık O(nmr) bulunur.

Eğer matrislerin her yöndeki boyutları n olursa, yürütme zamanı bağıntısındaki m ve r'ler yerine n yerleştirilip sadeleştirme işlemi yapılırsa,

T(n)= 3nnn+6nn+4n+2= 2n3+6n2+4n+2 ve O(n3)

bulunur.