logo

TechCodeview

Časová složitost smyčky, když se proměnná smyčky „rozšíří nebo zmenší“ exponenciálně

Pro takové případy je časová složitost smyčky O(log(log(n))). Následující případy analyzují různé aspekty problému. Pří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í být menší nebo roven n a máme 2klogk(log(n))= 2log(n)= n, což zcela souhlasí s hodnotou našeho posledního členu. Takže tam jsou v celkovém logk(log(n)) mnoho iterací a každá iterace trvá konstantní množství času, takže celková časová složitost je O(log(log(n))). Pří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 jsou v celkovém logk(log(n)) iterací a každá iterace trvá O(1), takže celková časová složitost je O(log(log(n))). V níže uvedeném článku naleznete analýzu různých typů smyček. https://www.geeksforgeeks.org/dsa/how-to-analyse-loops-for-complexity-analysis-of-algorithms/ Vytvořit kvíz