Si [math] k [/ math] es independiente del tamaño de entrada (es decir, es constante), no hay diferencia. Como estamos hablando de funciones de crecimiento, voy a asumir que su [math] k [/ math] es un entero positivo. Probémoslo usando la definición de Big-Oh. Mostraremos algo un poco más general para aclarar el punto, mostraremos [math] k \ in \ Theta (1) [/ math] (lo que significa que puede intercambiarlos, por lo tanto, no hay diferencia).
Dadas dos funciones de crecimiento [matemática] f (n) [/ matemática] y [matemática] g (n) [/ matemática], [matemática] f (n) \ en O (g (n)) [/ matemática] si y solo si existe un positivo real [matemática] c [/ matemática] y un entero positivo [matemática] n_0 [/ matemática], de modo que para todos [matemática] n \ geq n_0 [/ matemática], [matemática] f (n) \ leq c \ cdot g (n) [/ math].
Aplica la definición, vemos que necesitamos encontrar [matemáticas] c [/ matemáticas] y [matemáticas] n_0 [/ matemáticas], de modo que para todos [matemáticas] n \ geq n_0 [/ matemáticas], [matemáticas] 1 \ leq c \ cdot k [/ math]. Bueno, [math] k \ geq 1 [/ math] por definición, así que elija [math] c = 1 [/ math], luego [math] 1 \ leq 1 \ cdot k [/ math] si y solo si [math] 1 \ leq k [/ matemáticas]. Elija [math] n_0 = 1 [/ math] ya que la desigualdad se cumple para cualquier [math] n \ geq 1 [/ math]. Por lo tanto, según la definición de Big-Oh, [matemáticas] 1 \ en O (k) [/ matemáticas].
- ¿Hay algo que una máquina de Turing pueda calcular dado un tiempo infinito que no podría calcular en una cantidad de tiempo arbitrariamente grande?
- ¿Cuál es la diferencia entre la simulación de Monte Carlo y la simulación estocástica?
- Términos de Layman: ¿Qué es un filtro Bloom?
- ¿Qué pasaría si pudiéramos demostrar que AGI está más allá del poder computacional de la máquina Turing?
- ¿Es la matemática el lenguaje más difícil de entender?
Ahora mostraremos que [math] k \ en O (1) [/ math] (es decir, [math] 1 \ in \ Omega (k) [/ math]). Encuentre [math] c [/ math] y [math] n_0 [/ math] de modo que para todos [math] n \ geq n_0 [/ math], [math] k \ leq c \ cdot 1 [/ math]. Como [math] k [/ math] es una constante, seleccione [math] c = k [/ math], entonces tenemos que encontrar un [math] n_0 [/ math] tal que para todos [math] n \ geq n_0 [/ math], [math] 1 \ leq k \ cdot 1 [/ math] si y solo si [math] k \ leq k [/ math] si y solo si [math] 1 \ leq 1 [/ math], que claramente se cumple para todos [math] n \ geq 1 [/ math]. Elija [matemáticas] n_0 = 1 [/ matemáticas]. Por lo tanto, según la definición de Big-Oh, [math] k \ en O (1) [/ math].
Por lo tanto, [matemáticas] k \ in \ Theta (1) [/ matemáticas]. Vale la pena señalar que esto también significa, [matemáticas] 1 \ in \ Theta (k) [/ matemáticas] si no está familiarizado con Big-Theta. Esto significa que literalmente no hay diferencia . ¿Por qué quieres esto entonces? Recuerde que usamos asintóticos en la aplicación para comprender el comportamiento de los algoritmos con respecto a la entrada, las constantes no cambian con respecto a la entrada. Eso significa que cosas como [matemática] 1000000000 \ en O (1) [/ matemática] están bien y matemáticamente no hacen ninguna diferencia. Este es uno de los defectos del uso de los asintóticos, pero es natural para el estudio de la complejidad computacional con algoritmos.
