Aké sú náklady na spustenie nasledujúceho algoritmu? - algoritmus, časová zložitosť

for i=2 to n
j=3n
while j>=1 do
j=j/3

Aká by bola cena času spustenia daného algoritmu? Môžete nám opísať postupné riešenie.

odpovede:

Aby ste mohli vypočítať časovú zložitosť, obvykle chodíte z vnútorných slučiek do vonkajších slučiek.

Teraz vnútorné jeden je slučka. Končí, keď j < 1, to je prípad po O (log₃3n) kroky alebo O (1 + log₃ n) alebo O (log₃ n), Všimnite si, že tu používame n: počítadlo slučiek i vonkajšej slučky tu nehrá žiadnu úlohu.

Na vonkajšie slučka na druhej strane je iterovaná O (n-1) alebo tak O (n) a zakaždým robí to isté množstvo práce: O (log₃ n), Takže celková časová zložitosť je O (n log₃ n).

Môžete zapísať 3 do denníka, pretože O (log_kn) je O (log n) pre pevné k, Peknejšia notácia je O (n log n).