Почему данный алгоритм O (n ^ 2)?

Question

Я смотрю на алгоритм и пытаюсь сломать его и найти для него обозначение Big O. Однако я не могу понять, почему это O (n ^ 2)

Я вижу, что внешний цикл переходит в N, но внутренний цикл отбрасывает меня

int a = 0;
for (i = 0; i < N; i++) {
    for (j = N; j > i; j--) {
        a = a + i + j;
    }
}

Кто-нибудь знает, как мне лучше всего подойти к таким вопросам, если бы они появлялись на собеседовании? Я хочу стать лучше при анализе алгоритмов

Answer 1

Если вы визуальный человек, вы можете рассматривать внешний цикл как строки, а внутренний цикл как столбцы. Для каждой итерации внешнего цикла количество итераций (столбцов) во внутреннем цикле уменьшается на 1.

Представляя это визуально, вы получаете:

* * * * * 
  * * * * 
    * * * 
      * * 
        * 

Это половина квадрата (треугольника), поэтому примерно (n ^ 2) / 2, что равно O (n ^ 2).

Answer 2

Внешний цикл повторяется от 0 до N-1.

Внутренний цикл повторяется от N до i+1.

Это означает, что во время первой итерации внешнего цикла внутренний цикл выполняет N шагов. Во второй итерации внешнего цикла внутренний цикл выполняет N-1 шагов. В третьей итерации внешнего цикла внутренний цикл выполняет N-2 шагов. ... Это продолжается до последней итерации внешнего цикла, где внутренний цикл выполняет шаг 1.

Таким образом, общее количество шагов равно N + (N-1) + (N-2) + ... + 2 + 1 или (переупорядочено) 1 + 2 + ... + (N-1) + N. Эта сумма равна N * (N+1) / 2 ( подробности см. Здесь ), которая увеличивается до 0.5 * N^2 + 0.5 * N. Игнорирование более низких мощностей и постоянных факторов означает, что это в O (N ^ 2).