C ++ - обозначение Big-O

Question

По какой-то причине я не могу решить это. какой будет запись Big-o

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

Answer 1

for (int i = 0; i < n; i++)                  // N times
    for (int j = 0; j < n; j++) {            // N times (
        c[i][j] = 0;                         // Constant plus
        for (int k = 0; k < n; k++)          // N times
            c[i][j] += a[i][k] * b[k][j];    // Constant
    }                                        // )

Или O ( n · n · (1 + n · 1)), что эквивалентно O ( n · n · n ) или O ( n ³ ) после свертывания постоянных операций.

Answer 2

Ответ: O (n ^ 3)

Поскольку самый внешний цикл выполняется N раз.
Для каждого элемента в этом цикле средний цикл выполняется N раз.
Для каждого элемента в среднем цикле самый внутренний цикл выполняется N раз.

Всего циклов N * N * N = N ^ 3

Этот оператор выполняется N ^ 2 раза c[i][j] = 0;, но он не имеет значения по сравнению с внутренним оператором, который выполняется N ^ 3 раза.

Answer 3

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

Похоже, что O(n^3), потому что он имеет 3-уровневые циклы.

Answer 4

Способ решить эту проблему состоит в том, чтобы рассчитать количество операций в терминах n, а затем отбросить менее значимые термины (если они есть) ...