logo

TechCodeview

Časová zložitosť slučky, keď sa premenná slučky „expanduje alebo zmenšuje“ exponenciálne

Pre takéto prípady je časová zložitosť slučky O(log(log(n))). Nasledujúce prípady analyzujú rôzne aspekty problému. Prípad 1: CPP 
for (int i = 2; i <=n; i = pow(i k))  {   // some O(1) expressions or statements }
In this case i takes values 2 2k(2k)k= 2k2(2k2)k= 2k3... 2klogk(log(n)). Posledný člen musí byť menší alebo rovný n a máme 2klogk(log(n))= 2log(n)= n, čo úplne súhlasí s hodnotou nášho posledného člena. Takže tam sú v celkovom logk(log(n)) veľa iterácií a každá iterácia trvá konštantne dlho, kým prebieha, preto je celková časová zložitosť O(log(log(n))). Prípad 2: CPP 
// func() is any constant root function for (int i = n; i > 1; i = func(i))  {   // some O(1) expressions or statements }
In this case i takes values n n1/k(n1/k)1/k= n1/k2n1/k3... n1/klogk(log(n))takže sú v celkovom logk(log(n)) iterácií a každá iterácia trvá O(1), takže celková časová zložitosť je O(log(log(n))). V nižšie uvedenom článku nájdete analýzu rôznych typov slučiek. https://www.geeksforgeeks.org/dsa/how-to-analyse-loops-for-complexity-analysis-of-algorithms/ Vytvoriť kvíz