Es un poco complicado tener esta idea.
Déjame explicarte con una simple conversación entre p1 y p2.
p1: “¿Qué es la complejidad del tiempo? – Sumar dos números”
p2: “Es un solo paso, entonces O (1)”.
p1: “No es exactamente qué pasa si tengo un número muy grande, por lo que me llevará algún tiempo”.
p2: “Sí, depende del número. Depende de la longitud del número. Por lo tanto, será O (log N), tiene una complejidad de tiempo logarítmico”.
p1: “O deberíamos decir O (M) donde M = longitud de entrada, por lo que es además un algoritmo de tiempo lineal no un algoritmo de tiempo logarítmico”.
P2: “Ambos son lo mismo, solo una forma diferente de decir”.
p1: “Sí, pero para obtener una respuesta correcta, deberíamos revisar la definición de la notación O grande. Dice: la notación O grande se usa para clasificar los algoritmos según cómo responden a los cambios en el tamaño de entrada “.
p2: “¡Oh!”
p1: “¿Entonces si N como 130 o 200 afectará el tiempo de ejecución del algoritmo?”
p2: “No”
p1: “¿Entonces si N como 130 o 200000 afectará el tiempo de ejecución del algoritmo?”
p2: “Sí”
P1: “Entonces podemos decir que el tamaño de la entrada no es el valor de N sino el número de bits necesarios para representar N (aquí, representación binaria de N)”.
p2: “Entiendo el punto que está tratando de hacer. Así que la respuesta correcta debería ser lineal porque, según la definición, la gran O depende del tamaño de la entrada, no del valor de esas variables de entrada”.
p1: “Por lo tanto, es incorrecto usar una variable en notación O grande que no significa el tamaño de la entrada sino solo el valor de una de las entradas. Así que recuerde que cuando alguien le dice que la suma es operaciones O (n), no quiere decir n es el valor de la entrada, pero n denota el tamaño de la entrada (bits necesarios para representar N) “.
De manera similar, en este caso estamos diciendo que la complejidad temporal de la mochila es O (nW). Por lo tanto, el uso de W en la notación O grande debería generar señales de alerta porque W es solo un valor de una de las variables en la entrada y no tiene nada que ver (directamente) con el tamaño de la entrada.
Por lo tanto, la forma correcta de decir la complejidad de la mochila sería O (n * 2 ^ m) donde m es el número de bits en W. Ahora puede ver que la mochila tiene una complejidad exponencial.
Incluso cuando decimos que el problema de la mochila tiene complejidad O (nW) tenemos un término especial cuando usamos un valor de una variable, tiempo pseudo-polinomial.
- ¿Cómo funcionan los algoritmos de clasificación en un sistema distribuido grande?
- ¿Cuál es exactamente la diferencia entre f (n) yg (n)?
- ¿Cuál es el enfoque algorítmico para resolver el problema de hackerrank Substring Diff?
- Cómo contar el número de enteros palindrómicos dentro de un rango [A, B] donde A y B pueden ser de hasta 10 ^ 17
- Insertar un elemento en un montón toma O (log n). ¿Aún si insertamos n elementos en el montón, resulta ser O (n)?
