проанализировать сложность времени для этого короткого кода

Question

Я пытаюсь оценить сложность времени выполнения для этих нескольких строк кода, это код с пузырьковой сортировкой. теперь я знаю, что это O (n ^ 2), но я хочу провести точный анализ. и я не уверен, что все правильно понял

for i ← 1 to n-1
    for j ← n downto i+1
      if A[j-1] > A[j]
          temp ← A[j-1]
          A[j-1] ← A[j]
          A[j] ← temp

что я сделал: первая строка выполняется n раз, поэтому (c1) * n вторая строка зависит от i, но это будет n, тогда n-1, ..., 1 и вот где моя проблема, я должен использовать суммирование по мне? кажется странным, что время выполнения зависит от меня третья строка также зависит от массива, который мы получаем, и следующие строки зависят от этого.

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

Answer 1

Для каждого значения i код выполняет ряд операций, которые зависят от i, скажем c(i).Таким образом, общее количество операций будет

total := sum_{i=1}^{n-1} c(i)

. Теперь давайте вычислим c(i) для общего i.В худшем случае истинная ветвь оператора if всегда выполняется и принимает, скажем, C операций, что является величиной, независимой от j, i и n.Итак,

c(i) <= sum_{j=n}^{i+1} C
      = C*(n - (i+1) + 1)
      = C*(n - i)

Таким образом

total <= sum_{i=1}^{n-1} C*(n-i)
       = C * sum_{i=1}{n-1} (n-i)
       = C * n(n-1)/2
       = O(n^2)

Обратите внимание, что в лучшем случае истинная ветвь if никогда не произойдет, и вам нужно будет только принять необходимое количество операций.чтобы вычислить неравенство, скажите D.Следовательно, вы можете повторить тот же расчет, что и раньше, заменив C на D и <= на >=, чтобы получить

total >= O(n^2)