logo

TechCodeview

Tidskompleksitet af en løkke, når løkkevariabel "udvider eller formindsker" eksponentielt

I sådanne tilfælde er løkkens tidskompleksitet O(log(log(n))). De følgende tilfælde analyserer forskellige aspekter af problemet. Case 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)). Det sidste led skal være mindre end eller lig med n, og vi har 2klogk(log(n))= 2log(n)= n som stemmer fuldstændig overens med værdien af ​​vores sidste led. Så der er i alt logk(log(n)) mange iterationer, og hver iteration tager en konstant mængde tid at køre, derfor er den samlede tidskompleksitet O(log(log(n))). Tilfælde 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))så der er i alt logk(log(n)) iterationer og hver iteration tager tid O(1), så den samlede tidskompleksitet er O(log(log(n))). Se nedenstående artikel for analyse af forskellige typer sløjfer. https://www.geeksforgeeks.org/dsa/how-to-analyse-loops-for-complexity-analysis-of-algorithms/ Opret quiz