Сложность (вопрос начинающего) - PullRequest
Новая
       39

Сложность (вопрос начинающего)

2 голосов
/ 14 мая 2011

В чем сложность этих утверждений? 

for(int k = 1; k < n; k++)
    for(int i = 0; i < n-k; i++){
        //O(1) operation here
    }

Объяснение приветствуется.

1 Ответ

4 голосов
/ 14 мая 2011

Сначала войдите во внешний цикл, вы выполните операцию n-1 раз. Во-вторых, вы делаете это n-2 раза, ... Добавьте все это, и вы получите (n)*(n-1)/2 операций.

Чтобы увидеть эту сумму, запишите ее от 1 до (n-1), затем от (n-1) до 1 и добавьте каждый член по одному. 

  1   2   3 ... n-3 n-2 n-1
n-1 n-2 n-3 ...   3   2   1
---------------------------
  n   n   n       n   n   n

То есть 2 * sum = (n-1) * n.

Так что это примерно n² с точки зрения сложности.

...