Tengo un problema para determinar las complejidades de tiempo de los algoritmos.analizando la complejidad del tiempo de mis programas
for(int i=0;i <n i++){} O(n)
for(int i= 0 ;i<n ;i++){ O(n^2)
for(int j=0;j<n;j++){
}
}
ahora para siguiente código de cuál es la complejidad
for(i =0; i<n ; i++) {}
for (j=0;j<n ;j++) {}
es O (2n), ya que invloves 2 bucles separados?
¿qué sucede si comienzo j = 5 a n?
No hay O(2n), es solo O(n). En otras palabras, se escala a la misma velocidad que n.
Si era un anidado bucle, sería O(n2) pero la presencia de sus {} bloques vacíos significa que no está anidado.
Y no importa si comienza en uno o cinco, todavía se escala con n, solo con una constante constante ligeramente negativa. Por lo tanto, todavía O(n).
Las complejidades O(n), O(cn) y O(n+c) (donde c es una constante) son todos equivalentes. Además, generalmente también solo usa el término con el mayor efecto.
Por lo tanto, generalmente no verá O(7n3 + 3n2 + 12n + 2), que se simplificará a O(n3).
El resultado final es que a través de algunas matemáticas de lujo que no puedo recordar, puede convertir cosas como 2n en solo O grande (n). Los coeficientes se consideran constantes porque nos preocupa la complejidad y cuando tratamos solo con ese tema, necesitamos examinar la parte de una ecuación que causa el mayor crecimiento. En este caso, Big O (n^2) es el elemento más predominante dentro de la complejidad de la ecuación. Por lo tanto, su algoritmo se considera Big O (n).
mis disculpas, pequeño error basado en la lectura incorrecta de las últimas líneas de código. El que usted preguntó sería Big O (n)
Sí, es O (2n), pero eso es lo mismo que O (n), porque multiplicar por una constante no importa en complejidad asintótica. De manera similar, si omite los cinco primeros elementos, su ciclo toma O (n-5) tiempo, pero eso también es igual a O (n), porque sumar o restar una constante es aún más débil que multiplicar por una constante. Ver p. http://en.wikipedia.org/wiki/Big_O_notation para las definiciones.
No existe nada como O (2n). La complejidad del tiempo se refiere a cómo un algoritmo escala al infinito, no a su tiempo de ejecución real. En sus ejemplos, tiene dos bucles que son ambos lineales [O (n)] de tiempo, lo que significa que se escalarán linealmente con la entrada, por lo tanto, su algoritmo general es O (n).
Si comienza j = 5, sigue siendo O (n) porque sigue escalando linealmente.
Así que en esencia, O (2n) == O (n).
Hay dos reglas importantes de la Complejidad de tiempo que se aplica si y sólo si el valor de n es muy grande ...
El coeffeicient de la más alta término de orden puede ser descuidado.
Todos los términos de bajo pedido pueden ser igonados.
Por qué estos supuestos son bastante simples, Let `Veamos un ejemplo: -
Supongamos que la complejidad del tiempo es 5 n^2 + 3n. A valores muy bajos de n, el coeficiente y los términos de orden inferior se vuelven prominentes para un pequeño cambio en n. Pero supongamos que si el valor de n es muy grande, el efecto del término de orden inferior sobre la complejidad del tiempo es muy inferior y, además, el coeficiente del término de mayor orden también se puede ignorar de la misma manera.
Nota: la complejidad del tiempo juega un papel importante solo cuando n se acerca al infinito desde el punto de vista teórico.
Espero que estés claro ahora, no puedo encontrar la fuente donde leo esto. Tuve la misma duda hace un tiempo y en el artículo que mencionó claramente sobre el efecto y la importancia de la complejidad del tiempo en valores grandes de N. – NirmalGeo
La complejidad del tiempo juega un papel bastante importante mucho antes de que 'n' llegue a cualquier parte _cerca_ infinito :-) De lo contrario, no nos importaría en absoluto. – paxdiablo
La complejidad es la medida de la forma de la función que describe la relación de entrada ny el tiempo.
Tenga en cuenta que no hay una constante porque en la mayoría de los casos no se conoce la constante. Puede usar la constante si compara dos algoritmos comparables, pero en la mayoría de los casos citaría la complejidad genérica y mediría el tiempo con alguna entrada n. En su caso, O (2 * n) es igual a 2 * O (n) y esto es solo O (n) ya que 2 * O (n) no dice mucho como es y se puede comparar usando la constante 2 solo con anterioridad algoritmo. Decir que el segundo algoritmo tiene complejidad 2 * O (n) no tiene mucho sentido.
Mire la complejidad de esta manera.
Digamos que usted tiene un algoritmo que toma n = un millón. ¿Cuál es el tamaño aproximado o el orden de número de operaciones
O(n) -> 1e6 and this can be calculated in most cases
O(n * log(n)) -> 2*1e7 this can also be calculated in reasonable time.
O(n^2) -> 1e12 you will not be able to compute whit this algorithm in reasonable time
O(n^3) -> 1e18 here are so many operations that you have to think twice on how you are going to aproach this problem
am poco confundido lo que recibo de pensar es for (i = 0; i
jslearner