logo

TechCodeview

Tidskompleksiteten til en sløyfe når sløyfevariabelen "utvides eller krymper" eksponentielt

For slike tilfeller er tidskompleksiteten til løkken O(log(log(n))). Følgende tilfeller analyserer ulike aspekter av problemet. Tilfelle 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... 2kloggk(logg(n)). Det siste leddet må være mindre enn eller lik n og vi har 2kloggk(logg(n))= 2logg(n)= n som stemmer helt overens med verdien av vår siste term. Så det er i total loggk(log(n)) mange iterasjoner og hver iterasjon tar en konstant mengde tid å kjøre, derfor er den totale tidskompleksiteten O(log(log(n))). Tilfelle 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/kloggk(logg(n))så det er i total loggk(log(n)) iterasjoner og hver iterasjon tar tid O(1), så den totale tidskompleksiteten er O(log(log(n))). Se artikkelen nedenfor for analyse av ulike typer løkker. https://www.geeksforgeeks.org/dsa/how-to-analyse-loops-for-complexity-analysis-of-algorithms/ Lag quiz