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

Не искам да моля за помощ за нещо просто, но изглежда не мога да разбера как да отговоря на този въпрос.

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, тъй като съм свикнал да правя просто вложени сигма нотации for 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