какова временная сложность зависимого вложенного цикла? - PullRequest
Новая
       1

какова временная сложность зависимого вложенного цикла?

0 голосов
/ 10 февраля 2019

Не могли бы вы сказать мне, какова временная сложность цикла, Кажется, это O (n ^ 2), но я не знаю почему. 

int k=0;
for(int i = n / 2; i <= n; i++){
    for(j = 0; j <= i; j++){
        k++;
    }
}
  • n / 2
  • n / 2 + 1
  • n / 2 + 2 ...
  • n / 2 + n / 2

sum = n /2 + (n / 2 + 1) + (n / 2 + 2) + ... + (n / 2 + n / 2) = (n / 2 * n / 2) + (1 + 2 + ...+ n / 2) + n / 2 = 3/8 n ^ 2 + 3/4 n

Таким образом, сложность времени составляет O (n ^ 2) ???Это правильно?

1 Ответ

0 голосов
/ 10 февраля 2019

Как Ханьчжун упоминает в комментарии :

Да, это O(n^2).Нит - первый цикл итерации внешнего цикла n/2+1 times

O (n ^ 2) является правильным ответом.

...