5.2.1.3. Matris Toplama için T(n) Hesabı

Örnek: Aşağıda iki matrisi toplayıp üçüncü matrise yerleştiren toplaMatris(A, B; C) adlı bir fonksiyonun kodu görülmektedir. Bu fonksiyonun yürütme zamanını gösteren T(n) bağıntısı ayrık C dili deyimlerine göre belirleyiniz.

void toplaMatris(A, B, C)   int A[n][m], B[n][m], C[n][m];   {      int i, j;    for(i=0; i<n; i++)         for(j=0; j<m; j++)            C[i][j]=A[i][j]+B[i][j];   }

Çözüm: Burada içice döngü kurulmuştur. Birinci döngünün sayacı olan i matrisin satırına ikinci döngünün sayacı olan j ise sütuna karşılık düşmektedir. Buna göre 'de n çevrimlik döngü kurulmuştur ve for içerisinde yapılan işlem sayısı 2n+2 olur; 'de n çevrimlik döngü içerisinde m çevrimlik bir iç döngü kurulmuştur. Dolayısıyla toplam n.m çevrim yapılacaktır. 'deki işlem sayısı n.(2m+2) olur. 'de döngü içerisinde yalnızca toplama ve atama işleminden oluşan bir ayrık işlem vardır; ancak n.m çevrimlik döngü içerisinde olduğu için n.m maliyeti olur. Sonuç olarak toplam işlem maliyeti,

. satırda 2n+2 . satırda n.(2m+2) . satırda n.m     T(n) = 3nm+4n+2

olarak bulunur. Eğer n yerine satır, m yerine sütun yazılırsa bu denklem aşağıdaki gibi görülür:

T(satir, sütun) = 3satir.sütun + 4satir + 2                          (5.3)

Buradan görüldüğü T'nin bağımsız parametreler matrisin satır ve sütun bilgileridir. Eğer matrisler birer kare matris iseler, yani n=m ise, bu durumda yürütme zamanı bağıntısı,

T(n) = 3n² + 4n + 2                          (5.4)

gibi olur. Bu bir ikinci dereceden denklemdir.