Асимптотика c анализ гнезда l oop с условием (j = i + 1)

Question

Я пытаюсь понять пример большого O на этой странице: http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html

for (i = 0; i < N; i++) {
   for (j = i+1; j < N; j++) {
      sequence of statements }
}

Я не понимаю, почему внутренний l oop будет работать для N если i=0. Если i=0, то j=1, и, как результат, число итераций для внутреннего l oop должно составлять N-1. Я понимаю, почему сложность этого l oop равна O(n^2). Я не понимаю, почему внутренний l oop начинается с N числа итераций, а не N-1.

Answer 1

В вашей ссылке есть небольшая ошибка. Действительно, внутренний l oop начинается с N-1 итераций, а не N, но результат остается тем же.

Начиная с этой первой ошибки, они пропускают 1 на каждой итерации. Они забыли +1, j=i+1 Я думаю.

Answer 2

Big-O для этого O(n^2).

Внешний l oop равен O(n), а внутренний O(n - 1).

Таким образом, эффективная сложность времени равна O(n^(n - 1)) = O(n^2 - n).

Теперь для большего значения n значение n^2 будет значительно выше, чем у n и net результат будет зависеть от n^2

Следовательно, сложность времени будет O(n^2)