logo

TechCodeview

Complejidad temporal de un bucle cuando la variable del bucle se "expande o se contrae" exponencialmente

Para tales casos, la complejidad temporal del bucle es O (log (log (n))). Los siguientes casos analizan diferentes aspectos del problema. Caso 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... 2kregistrok(registro(n)). El último término debe ser menor o igual a n y tenemos 2kregistrok(registro(n))= 2registro(n)= n que concuerda completamente con el valor de nuestro último término. Entonces hay en total registrok(log(n)) muchas iteraciones y cada iteración requiere una cantidad de tiempo constante para ejecutarse, por lo tanto, la complejidad del tiempo total es O(log(log(n))). Caso 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(norte1/k)1/k= norte1/k2norte1/k3... norte1/kregistrok(registro(n))entonces hay en total registrok(log(n)) iteraciones y cada iteración toma tiempo O(1), por lo que la complejidad del tiempo total es O(log(log(n))). Consulte el artículo siguiente para analizar diferentes tipos de bucles. https://www.geeksforgeeks.org/dsa/how-to-analyse-loops-for-complexity-analysis-of-algorithms/ Crear cuestionario