Продолжительность цикла

Question

Просмотр примеров и объяснение времени выполнения вложенных циклов для http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L03-BigOh.htm#Counting,, а второй пример мне не подходит.

пример 1

sum = 0;  
for( i = 0; i < n; i++)  
    for( j = 0; j < n; j++)  
        sum++;

Имеет смысл сразу. Снаружи для цикла O (n). Внутренний цикл - это O (n). Умножьте их вместе, O(n) * O(n) = O(n*n) = O(n^2).

Второй пример. Внутренний цикл не начинается с 0.

sum = 0;  
for( i = 0; i < n; i++)  
    for( j = i; j < n; j++)  
        sum++;

Время выполнения внутреннего цикла будет ( 1 + 2 + … + n) = n*(n+1)/2 = O(n^2) Как и в первом примере, внешний цикл работает с O (n). Поэтому общее время работы составляет O(n) * O(n^2) = O(n^3). Я прав, или я что-то упустил? Спасибо!

Answer 1

(1 + 2 + … + n) = n*(n+1)/2 = O(n^2) - это общее время для программы. Вам не нужно затем умножать его на O(n) для внешнего цикла; вы уже учли внешний цикл.

[Примечание: технически, можно сказать, что алгоритм O(n^3). Это немного вводит в заблуждение.]

Answer 2

Вы добавляете общее время выполнения внутреннего цикла, а не время работы за итерацию внешнего цикла . Время выполнения внутреннего цикла на внешнюю итерацию по-прежнему равно O (n), что приводит к общему результату O (n ² ).

Другими словами, если вы понимаете первый пример, а второй пример меньше работает, чем первый пример, как он может иметь большую сложность?

Answer 3

Время выполнения внутреннего цикла составляет в среднем около n / 2, так что это все равно O (n), так же, как в первом примере.

Answer 4

Ответ на первые два ответа выше.Я не вижу, как (1 + 2 + … + n) = n*(n+1)/2 = O(n^2) будет общее время работы

Скажем, n = 3

sum = 0;  
for( i = 0; i < n; i++)  
    for( j = i; j < n; j++)  
        sum++;

Общее время работы для внутреннего цикла составляет 1 раз+ 2 раза + 3 раза

Итак, где внешний цикл вступает в игру?Он также выполняется O (n) раз (как это было в первом примере)