logo

TechCodeview

Silmukan aika monimutkaisuus, kun silmukkamuuttuja "laajenee tai kutistuu" eksponentiaalisesti

Tällaisissa tapauksissa silmukan aikamonimutkaisuus on O(log(log(n))). Seuraavat tapaukset analysoivat ongelman eri puolia. Tapaus 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... 2klokik(log(n)). Viimeisen termin on oltava pienempi tai yhtä suuri kuin n, ja meillä on 2klokik(log(n))= 2loki(n)= n, joka on täysin yhtäpitävä viimeisen termimme arvon kanssa. Lokia on siis yhteensäk(log(n)) monta iteraatiota ja jokaisen iteroinnin suorittamiseen kuluu vakioaika, joten kokonaisajan monimutkaisuus on O(log(log(n))). Tapaus 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/klokik(log(n))joten lokia on yhteensäk(log(n)) iteraatiot ja jokainen iteraatio vie aikaa O(1), joten kokonaisajan monimutkaisuus on O(log(log(n))). Katso alla olevasta artikkelista erityyppisten silmukoiden analysointi. https://www.geeksforgeeks.org/dsa/how-to-analyse-loops-for-complexity-analysis-of-algorithms/ Luo tietokilpailu