Notación de Little-Oh en detalle, tarea de CS, excluyendo la tarea real

Question

Estoy sentado aquí con esta tarea en un curso de algoritmos con conjuntos de datos masivos y el uso de notación de Little-Oh me ha confundido, aunque estoy perfectamente seguro con Big-Oh.

No quiero una solución a la tarea, y como tal no la presentaré. En cambio, mi pregunta es cómo interpreto la complejidad del tiempo o (log n)?

Sé por la definición, que un algoritmo A debe crecer asintóticamente más lento que O (log n), pero no estoy seguro de si esto significa que el algoritmo debe estar funcionando en un tiempo constante o si aún se permite que log n bajo ciertas condiciones, de modo que c = 1 o si realmente es Log (N-1).

Decir que un algoritmo tiene un tiempo de ejecución de O (log n) pero de hecho hace dos iteraciones y como tal C = 2, pero 2*log n es todavía O (log n), ¿Tengo razón cuando digo que esto no es válido para Little-Oh?

Se aprecia mucho cualquier ayuda y, si se necesita estrictamente para aclarar, proporcionaré la tarea

Answer 1

Para decir el f es 'little-oh-of g' f = o(g), significa que el cociente

|f(x)/g(x)|

se acerca a 0 como x se acerca al infinito. Refiriéndose a su ejemplo de o(log n), esa clase contiene funciones como log x / log (log x), sqrt(log x) Y muchos más, entonces o(log x) Definitivamente no implica O(1). Por otra parte, log (x/2) = log x - log 2, asi que

log (x/2) / log x = 1 - log 2 / log x -> 1

y log (x/2) no esta en la clase o(log x).

Answer 2

Para Little-Oh, F (x) no tiene que ser más pequeño que G (x) para todo x. Tiene que ser más pequeño solo después de un cierto valor de x. (Para su pregunta, todavía se permite que se registre bajo ciertas condiciones).

Por ejemplo:

 let f(x) = 5000x and g(x) = x^2

f (x) / g (x) A medida que X se acerca al infinito es 0, entonces f (x) es litte-o de g (x). Sin embargo, en x = 1, F (x) es mayor que g (x). Solo después de que X se vuelve mayor que 5000 será G (x) más grande que F (x).

Lo que realmente nos dice que G (X) siempre crece a un ritmo más rápido que F (X). Por ejemplo, mira cuánto F (x) creció entre x = 1 y x = 2:

 f(1) = 5000
 f(2) = 10000 - f(x) became twice as big

Ahora mira G (x) en el mismo intervalo:

 g(1) = 1
 g(2) = 4 - g(x) became four times bigger

Esta tasa aumentará aún más a valores más grandes de x. Ahora, dado que G (x) aumenta a un ritmo más rápido y debido a que llevamos X al infinito, en algún momento se volverá más grande que F (x). Pero esto no es lo que le preocupa poco a, se trata de la tasa de cambio.