Расчет времени выполнения цикла

Question

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

Я дал код: который в основном psedocode

function generalFunction(value) 
    for(i=1 to value.length-1)// value is an array, and this runs `n-1 Times` 
    for(j=1 to value.length-i // This runs `n-1(n-1)` times? 
     if value[j-1] > value[j] //This runs n^2 times? 
     swap A[j+1] and value[j] //How would would this run? 

Для первой строки, я подсчитал, что он работает n-1 раз. Поскольку цикл идет n раз, но поскольку мы вычитаем 1 из длины массива arbritray, это будет n-1 раз (я считаю).

То же самое можно сказать и для второй строки, за исключением того, что мы должны умножить ее на исходный цикл.

Однако, я не уверен в последних двух строках, будет ли третий работать в n^2 раза? Я написал n^2 из-за двух вложенных циклов. Я не уверен, как подойти к последней строке, любой вклад будет очень оценен.

Answer 1

Да, это будет работать в n^2 - согласно вашим комментариям. Обратите внимание, что выполнение внутреннего оператора if (swap) не имеет отношения к тому, что двойной цикл выполняется n^2 раза. Кроме того, минус одна часть (n-1) все еще делает ее n^2, так как вы в основном ищете аппроксимацию сверху ~, а n^2 является самой узкой такой границей. В основном (n-1) (n-1) = n^2 - 2n +1 доминирует n^2 член.

Для определения и работоспособный пример подобного этому см Wikipedi - example section

P.S. Ошибка O - это сценарий -worst-case. Поэтому в худшем случае оператор if всегда будет правдой, поэтому swap попадет в каждый цикл цикла. это означает, что если вы нажмете точку останова, она будет удалена (n-1) * (n-1) раз. Разлагая это означает, что n^2 - 2n + 1 раз.