Временная сложность фрагмента псевдокода

Я не хочу просить о помощи с чем-то простым, но я не могу понять, как ответить на этот вопрос.

Compute the time complexity of the following program 
fragment: 
sum = 0; 
for i=1 to n do 
  for j=1 to i do 
    k = n*2 
    while k>0 do 
      sum=sum+1; 
      k = k div 2;

Я понимаю, что то, что находится внутри цикла while, занимает O (1), цикл while занимает O (logn), но тогда я не понимаю, как это соединяется с вложенными циклами for, поскольку я привык просто делать вложенные сигма-нотации для петель.

Спасибо!


performance time-complexity pseudocode
person user1901074    schedule 04.03.2014    source источник
comment
@herohuyongtao Прости! Исправил это   -  person user1901074    schedule 04.03.2014
comment
обратите внимание, что во внутреннем цикле условие остановки возникает, когда k достигает 0 или ниже. если k — положительное целое число, в какой-то момент оно достигнет 1 (или будет округлено до 1), а затем делится на 2, что дает 0,5 и может быть снова округлено до 1 (зависит от того, как вы решите выполнить округление), который создает бесконечный цикл. Если k — действительное число, то оно в любом случае никогда не достигнет 0 или ниже (если оно началось с положительного значения).   -  person Ron Teller    schedule 04.03.2014

Ответы (2)


arrow_upward
1
arrow_downward

Формальная демонстрация, которая шаг за шагом показывает порядок роста вашего алгоритма:

введите здесь описание изображения

person Mohamed Ennahdi El Idrissi    schedule 15.03.2014

arrow_upward
1
arrow_downward

Вот несколько советов, как разобрать сложность этой функции:

  1. Посмотрите на внутренний цикл, где k=n*2. Предположим, что n=8, поэтому k=16, k продолжает делиться на 2, пока не станет 0 или меньше (здесь я предполагаю, что округление 0,5 дает 0). Таким образом, ряд, описывающий k до конца цикла, будет 16,8,4,2,1,0. попробуйте подумать, какая функция описывает количество элементов в этой серии, если вы знаете, что первое значение равно k.

  2. У вас есть два вложенных цикла for, первый цикл просто повторяется n раз, затем второй (внутренний) цикл повторяется до тех пор, пока не достигнет номера итерации первого цикла (представленного i), что означает, что сначала он будет повторяться один раз, затем дважды и так далее до n. Таким образом, количество итераций, выполненных вторым циклом, можно описать рядом: 1, 2, 3, ... , n. Это очень простая арифметическая прогрессия, и сумма этого ряда даст вам общее количество итерации внутреннего цикла for. Это также количество вызовов внутреннего цикла while (на которое не влияет номер текущей итерации, поскольку k зависит от n, которое является постоянным, а не от i или j).

person Ron Teller    schedule 04.03.2014