Resultados de la búsqueda a petición "big-o"
¿Cómo puedo desplegar la recurrencia: T (n) = 2T ((n + 2) / 3)
Estoy tratando de resolver esta recurrencia, pero no sé cómo desplegarla. T(n)=2T((n+2)/3) + 1¿Puedo ignorar ese "+2" y resolverlo como si fuera 2T (n / 3) + 1? Esto proviene de un problema que usa unV[a..b] matriz y hace este regreso: return ...
¿Cómo la complejidad temporal del siguiente código es O (n)?
Estaba resolviendo una pregunta de complejidad temporal en Bit de entrevista, que se muestra a continuación en la imagen. [/imgs/xwyZQ.png] La respuesta correcta a esta pregunta es O (N). Pero según yo, la respuesta debería ser O (NlogN). Dado ...
Complejidad espacial de la función recursiva
Dada la función a continuación: int f(int n) { if (n <= 1) { return 1; } return f(n - 1) + f(n - 1); }Sé que la complejidad del tiempo Big O esO(2^N), porque cada llamada llama a la función dos veces. Lo que no entiendo es por qué la ...
Complejidad computacional de un algoritmo de ruta más larga con un método recursivo
Escribí un segmento de código para determinar la ruta más larga en un gráfico. El siguiente es el código. Pero no sé cómo obtener la complejidad computacional debido al método recursivo en el medio. Como encontrar el camino más largo es ...
Complejidad temporal del triple for-loop dependiente y condicional
for i in xrange(1,n+1): for j in xrange(1,i*i): if j%i==0: for k in xrange(0,j): print("*")¿Cuál será la complejidad temporal del algoritmo anterior?
demostrar que la comparación máxima de la construcción de almacenamiento dinámico binario es (2N-2)
Estoy tratando de demostrar que para montones binarios, buildHeap hace a lo sumo (2N-2) comparaciones entre elementos. Me resulta muy difícil probar esta afirmación.
Demuestre que g (n) es O (g (n)) para cada uno de los siguientes [cerrado]
2^(sqrt(log(n)) esO(n(^4/3)) n^(4/3) esO(n(log(n))^3) n(log(n))^3) esO(n^(log(n)) n^(log(n)) esO(2^n) Puedo hacerlo por ellos cuando tienen la misma base; No puedo entenderlo cuando no tienen la misma base; sé que todo esto es cierto.
¿Cómo es la complejidad de la clasificación de cubetas O (n + k) si implementamos cubetas usando listas vinculadas?
Tengo curiosidad acerca de por qué la clasificación de cubetas tiene un tiempo de ejecución de O (n + k) si utilizamos cubetas implementadas con listas vinculadas. Por ejemplo, supongamos que tenemos esta entrada: n = no of element= 8 k = range ...
La complejidad del tiempo para el método babilónico
¿Cuál sería la complejidad del tiempo para el método babilónico? es log (n) donde n es el número para el que queremos encontrar la raíz cuadrada? Si es así, ...
Necesito ayuda para demostrar que si f (n) = O (g (n)) implica 2 ^ (f (n)) = O (2 ^ g (n)))
En un problema anterior, mostré (con suerte correctamente) que f (n) = O (g (n)) implica lg (f (n)) = O (lg (g (n))) con condiciones suficientes (por ejemplo...