BigO tiempo de ejecución en algunos métodos

Question

Ok, estos son métodos bastante simples, y hay algunos, por lo que no quería simplemente crear varias preguntas cuando son todas la misma cosa. BigO es mi debilidad Simplemente no puedo entender cómo surgen estas respuestas. ¿Hay alguna forma de que pueda darme una idea de su pensando en analizar los tiempos de ejecución de algunos de estos métodos? ¿Cómo lo descomponen? ¿Cómo debería pensar cuando veo algo como esto? (específicamente el segundo, no entiendo cómo es eso O (1))

Answer 1

function f1: 
    loop 3 times 
    loop n times 

Por lo tanto, O (3 * n) que es efectivamente O (n).

---

function f2: 
    loop 50 times 

O (50) es efectivamente O (1).

Sabemos que se repetirá 50 veces porque irá hasta que n = n - (n/50) sea 0. Para que esto sea cierto, debe iterar 50 veces (n - (n/50)*50 = 0).

---

function f3: 
    loop n times 
    loop n times 

Por lo tanto O (n^2).

---

function f4: 
    recurse n times 

Esto se sabe porque peor de los casos es que n = alto - bajo + 1. El desconocimiento del 1. Eso significa que n = alto - bajo.

Para terminar,

arr[hi] * arr[low] > 10 

suponer que esto no se produce hasta baja se incrementa con la más alta que puede ir (alto).

Esto significa n = alto - 0 y debemos volver a recurrir hasta n veces.

---

function 5: 
    loops ceil(log_2(n)) times 

Sabemos esto debido a la m/=2.

Por ejemplo, deje n = 10. log_2 (10) = 3.3, cuyo límite máximo es 4.

10/2 = 
    5/2 = 
    2.5/2 = 
    1.25/2 = 
     0.75 

En total, hay 4 iteraciones.

Answer 2

El segundo es 50 porque el gran O es una función de la longitud de la entrada. Es decir, si el tamaño de entrada cambia de 1 millón a 1 mil millones, el tiempo de ejecución debería aumentar en 1000 si la función es O (N) y 1 millón si es O (n^2). Sin embargo, la segunda función se ejecuta en tiempo 50 independientemente de la longitud de entrada, por lo que es O (1). Técnicamente sería O (50) pero las constantes no importan para O grande

Answer 3

Obtiene un análisis n^2 al realizar un ciclo dentro de un ciclo, como el tercer método. Sin embargo, el primer método no analiza n^2 porque el primer ciclo se define como tres veces. Esto hace que el tiempo para el primero sea 3n, pero no nos importan los números para Big-O.

El segundo, presenta un paradigma interesante, donde a pesar de que tiene un bucle único, el análisis de temporización sigue siendo O (1). Esto se debe a que si tuviera que trazar el tiempo necesario para realizar este método, no se comportaría como O (n) para números más pequeños. Para números más grandes, se vuelve obvio.

Para el cuarto método, tiene un tiempo O (n) porque su función recursiva está pasando lo + 1. Esto es similar a si estaba usando un ciclo for e incrementa con lo ++/++ lo.

La última tiene un tiempo O (log n) porque divide su variable por dos. Solo recuerde que cualquier cosa que le recuerde a una búsqueda binaria tendrá un tiempo de registro n.

También hay otro truco para el análisis de temporización. Supongamos que tiene un bucle dentro de un bucle, y dentro de cada uno de los bucles estaba leyendo líneas de un archivo o apareciendo elementos de una pila. En realidad, esto solo sería un método O (n), ya que un archivo solo tiene una cierta cantidad de líneas que puede leer, y una pila solo tiene una cierta cantidad de elementos que puede expulsar.

Answer 4

La idea general de la notación de O grande es la siguiente: da una respuesta aproximada a la pregunta "Si le dan un conjunto de N elementos, y tiene que realizar alguna operación repetidamente con estos elementos, ¿cuántas veces? ¿Necesitarás realizar esta operación? Digo una respuesta aproximada, porque (la mayoría de las veces) no da una respuesta precisa de "5 * N + 35", sino solo "N". Es como un estadio de béisbol. Realmente no te importa la respuesta precisa, solo quieres saber qué tan grave será cuando N se agrande. Entonces las respuestas como O (N), O (N * N), O (logN) y O (N!) Son típicas, porque cada una representa una especie de "clase" de respuestas, que se pueden comparar entre sí. Un algoritmo con O (N) funcionará mucho mejor que un algoritmo con O (N * N) cuando N sea lo suficientemente grande, no importa cuán larga sea la operación en sí misma.

Así que lo analizo así: Primero identifique lo que será la N. En los ejemplos anteriores, es bastante obvio: es el tamaño de la matriz de entrada, porque eso determina cuántas veces realizaremos un ciclo. A veces no es tan obvio, y a veces tienes múltiples datos de entrada, así que en lugar de solo N, también obtienes M y otras letras (y luego la respuesta es algo así como O (N * M * M)).

Luego, cuando tengo mi N descifrado, trato de identificar el ciclo que depende de N. En realidad, estas dos cosas a menudo se identifican juntas, ya que están muy unidas.

Y, por supuesto, tengo que averiguar cuántas iteraciones hará el programa según N. Y para hacerlo más fácil, realmente no intento contarlas, solo trato de reconocer las respuestas típicas - O (1), O (N), O (N * N), O (logN), O (N!) O tal vez algún otro poder de N. El O (N!) Es bastante raro, porque es muy ineficiente , que implementarlo sería inútil.

Si obtiene una respuesta de algo como N * N + N + 1, simplemente descarte las más pequeñas, porque, de nuevo, cuando N se hace grande, las demás ya no importan. E ignore si la operación se repite un número fijo de veces. O (5 * N) es lo mismo que O (N), porque es el estadio que estamos buscando.

Agregado: Como se le preguntó en los comentarios, aquí están los análisis de los dos primeros métodos:

El primero de ellos es fácil. Solo hay dos bucles, el interno es O (N), y el externo simplemente lo repite 3 veces. Entonces sigue siendo O (N). (Recuerde - O (3N) = O (N)).

El segundo es complicado. No estoy realmente seguro de eso. Después de mirarlo por un tiempo, entendí por qué bucles solo 50 veces. Como esto no depende de N en absoluto, cuenta como O (1). Sin embargo, si fuera a pasarlo, por ejemplo, una matriz de solo 10 elementos, todos positivos, entraría en un ciclo infinito. Eso es O (∞), supongo. Entonces, ¿cuál es? No sé ...

No creo que haya una forma formal de determinar el número de la O grande para un algoritmo. Es como el problema de detenerse. De hecho, pensándolo bien, si pudieras determinar universalmente la gran O por un trozo de código, también podrías determinar si alguna vez se detiene o no, contradiciendo así el problema de detención. Pero eso es solo mis reflexiones.

Por lo general, solo voy por ... no sé, como una especie de "corazonada". Una vez que "obtienes" lo que representa el Big-O, se vuelve bastante intuitivo. Pero para algoritmos complicados, no siempre es posible determinarlo. Tome Quicksort, por ejemplo. En promedio, es O (N * logN), pero dependiendo de los datos puede degradarse a O (N * N). Sin embargo, las preguntas que obtendrá en la prueba deben tener respuestas claras.