Большая-O сложность вложенных для циклов

Question

Большая-O сложность вложенных для циклов

Я смущен сложностью следующего (операция, выполненная во внутреннем цикле, находится в постоянное время):

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

этот O (n^2) или O (n)? Я рисунок O (n^2). Какие-либо идеи?

также следующее делает меня любопытным:

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

9

big-o nested-loops

задан Greg Hewgill 8 August 2010 в 02:43

2 ответа

Вы правы, эти вложенные циклы по-прежнему равны O (n ^ 2). Фактическое количество операций примерно равно (n ^ 2) / 2, что после отбрасывания постоянного коэффициента 1/2 составляет O (n ^ 2).

3

ответ дан 4 December 2019 в 13:44

Другие вопросы по тегам:

big-o nested-loops

Похожие вопросы:

score 12 · Accepted Answer

Определенно O (n в квадрате) , конечно. Краткое объяснение для обоих случаев: 1 + 2 + ... + n равно n (n + 1) / 2 , то есть (n в квадрате плюс n) / 2 (и в big-O мы опускаем вторую, меньшую часть, так что у нас остается n в квадрате / 2, что, конечно, равно O (n в квадрате) ).