ZEITKOMPLEXITÄT EINER SCHLEIFE, WENN SICH DIE SCHLEIFENVARIABLE EXPONENTIELL „ERWEITERT ODER VERKLEINERT“.

In solchen Fällen beträgt die Zeitkomplexität der Schleife O(log(log(n))). In den folgenden Fällen werden verschiedene Aspekte des Problems analysiert. Fall 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 2^k(2^k)^k= 2^k²(2^k²)^k= 2^k³... 2^k^{^{Protokoll_k(log(n))}}. Der letzte Term muss kleiner oder gleich n sein und wir haben 2^k^{^{Protokoll_k(log(n))}}= 2^log(n)= n, was völlig mit dem Wert unseres letzten Termes übereinstimmt. Es gibt also insgesamt Protokoll_k(log(n)) viele Iterationen und jede Iteration benötigt eine konstante Zeit für die Ausführung, daher beträgt die Gesamtzeitkomplexität O(log(log(n))). Fall 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 n^1/k(N^1/k)^1/k= n^1/k²N^1/k³... N^{1/k^{Protokoll_k(log(n))}}es gibt also insgesamt log_k(log(n)) Iterationen und jede Iteration benötigt Zeit O(1), sodass die Gesamtzeitkomplexität O(log(log(n))) beträgt. Im folgenden Artikel finden Sie eine Analyse verschiedener Arten von Schleifen. https://www.geeksforgeeks.org/dsa/how-to-analyse-loops-for-complexity-analysis-of-algorithms/ Quiz erstellen

TechCodeview

Zeitkomplexität einer Schleife, wenn sich die Schleifenvariable exponentiell „erweitert oder verkleinert“.