Время выполнения этого псевдокода

Question

Может ли кто-нибудь помочь мне проанализировать время выполнения следующего псевдокода

for(i = 0; i < n*n*n; i++)
    for(j = i; j < n; j++)
        x++

То, как я вижу, это омега (n ^ 3) для нижней границы, поскольку это то, что было бы, если бы внутри внешнегоцикл for был просто theta (1).

Меня смущает внутренний цикл, который выполняется только для первых n итераций внешнего цикла.Я просто усредняю ​​время выполнения внутреннего цикла: n ^ 3 * ((1 / n ^ 2) * n + (1 / n) * 1, в этом случае это O (n ^ 3)?

Answer 1

Зависит от того, насколько умен ваш компилятор.Алгоритмы могут быть разделены на две части (это может быть связано с одной ошибкой, но вы поймете идею)

// i<n
// O(n^2)
for( i=0; i<n ; ++i )
  for( j=i; j<n; ++j )
    x++

// n < i < n*n*n
// O(n^3)
for( i=n ; i<n*n*n; ++j)
  noop(); //do nothing

Для i > n вторая часть ничего не делает, поэтому умный компилятор будет выполнять только циклк n, в этом случае это O (n ^ 2).

Однако, если ваш компилятор не умен, вторая половина тоже выполнится, и вы просто получите сравнение O (1) и общее поведениеявляется O (n ^ 3).

Answer 2

Внутренний цикл будет выполняться только если i<n. Так что это O(n^2).

Answer 3

Ваш алгоритм должен быть рассмотрен следующим образом:

for(i = 0; i < n*n*n; i++) {
    for(j = i; j < n; j++) {
        x++
    }
    if (i >= n) {
        y ++;
    }
}

Где x вычисляет количество как внутренних, так и внешних циклов, а y будет рассчитывать количество итераций внешнего цикла, когдавнутренний цикл больше не должен выполняться.

Таким образом, вы можете формально действовать следующим образом:

Когда n = 10, результат будетbe: x = 55 и y = 990, что совместимо с приведенной выше формулой.