Время выполнения и тета-нотация

Question

для следующего кода:

for(i=0;i<5;i++)
 for(j=2;j<n;j++)
  {
      c[i][j]=0;
       for(k=0;k<n;k++)
       c[i][j]=a[i][k]*b[k][j];
  }

Я бы сказал, что время выполнения - тета (n ^ 3), как я вижу в цикле k, есть два n (n ^ 3) идругой цикл, другой n, что делает его n ^ 3.Будет ли это правильно или что я пропустил.

Спасибо

Answer 1

Вот ваш код в формате:

for (i=0; i < 5; i++) {
    for (j=2; j < n; j++) {
        c[i][j] = 0;
        for (k=0; k < n;k++)
            c[i][j] = a[i][k]*b[k][j];
    }
}

Внешний цикл в i повторяется только 5 раз, и поэтому может рассматриваться как постоянное наказание, если речь идет о сложности.Внутренние два цикла в j и k не зависят друг от друга, и оба - O(n).Поэтому мы можем просто умножить сложности, чтобы получить O(n^2) для общего времени работы как функцию n.