logo

TechCodeview

A hurok időbeli összetettsége, amikor a hurokváltozó exponenciálisan „tágul vagy zsugorodik”

Ilyen esetekben a hurok időbonyolultsága O(log(log(n))). A következő esetek a probléma különböző aspektusait elemzik. 1. eset: 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)). Az utolsó tagnak kisebbnek vagy egyenlőnek kell lennie n-nél, és 2-t kapunkklogk(log(n))= 2log(n)= n, ami teljesen megegyezik utolsó tagunk értékével. Tehát vannak összesen naplóbank(log(n)) sok iteráció, és minden iteráció állandó időtartamot vesz igénybe, ezért a teljes időbonyolultság O(log(log(n))). 2. eset: 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))tehát összesen naplóban vannakk(log(n)) iterációk és minden iteráció O(1) időt vesz igénybe, így a teljes időbonyolultság O(log(log(n))). Tekintse meg az alábbi cikket a különböző típusú hurkok elemzéséhez. https://www.geeksforgeeks.org/dsa/how-to-analyse-loops-for-complexity-analysis-of-algorithms/ Kvíz létrehozása