Notación Theta en tiempo constante. ¿Por qué usamos el 1?

En notación asintótica, cuando se afirma que si el tamaño del problema es lo suficientemente pequeño (por ejemplo, n<cpara alguna constante c), la solución toma tiempo constante y se escribe como Theta(1).
¿Por qué escribimos 1 dentro del Theta?
¿Qué significa 1eso? ¿Por qué no Theta(c)?

Esas anotaciones están destinadas a denotar el crecimiento asintótico. Las constantes no crecen y, por lo tanto, es bastante igual qué constante eliges. Sin embargo, hay una convención que elige 1 para indicar que no hay crecimiento.

Supongo que esto se debe al hecho de que desea simplificar los términos matemáticos en cuestión. Cuando tenga un factor constante, simplemente divídalo entre él y todo lo que queda es 1. Esto facilita las comparaciones.

Ejemplo:

O (34 * n ^ 2) = O (1 * n ^ 2) = O (n ^ 2)

y

O (2567.2343 * n ^ 2/5) = O (n ^ 2)

¿Ves lo que quiero decir? A medida que estos términos matemáticos se vuelven cada vez más complicados, no desea tener constantes ruidosas cuando no son relevantes para la información que le interesa. ¿Por qué debería escribir O (2342.4534675767) cuando puede expresarse más fácilmente con O (1), que comunica los hechos del caso sin ambigüedades.

Además, el artículo de Wikipedia sobre la complejidad del tiempo también implica que es una convención:

Se dice que un algoritmo es tiempo constante (también escrito como O (1) tiempo) ...

Todo esto es muy ondulado, pero hay una razón matemática por la que no usamos Theta (c) y en su lugar usamos Theta (1). Usaré la notación Big O para mostrar esto.

Tiene que ver con una propiedad de notación Big Theta (así como Big O y Big Omega). Si tiene una función con tasa de crecimiento O(g(x))y otra con tasa de crecimiento O(c * g(x))donde ces constante, diría que tienen la misma tasa de crecimiento. Es decirO(c * g(x)) = O(g(x))

Podemos decir esto porque la definición de la notación Big O ( f(x) = O(g(x))) significa que tenemos una función f(x)y función g(x)tal que |f(x)| <= k * |g(x)|para algunos kvalores constantes y lo suficientemente grandes de x. Al multiplicar por la constante c, tendríamos:

O(c * g(x)) => k * |c * g(x)| = k * |c| * |g(x)| <= k' * g(x) dónde k' = k * |c|

Tenga en cuenta que |k' * g(x)| <= k'' g(x)para algunos k''valores constantes y lo suficientemente grandes de x, lo que significa que k' * g(x)crece a un ritmo de O(g(x))y, por lo tanto,O(c * g(x)) = O(g(x))

Cuando g(x) = 1tenemos O(1)crecimiento, decir que el O(c)crecimiento por cierto valor cno nos dice nada porque la constante ya está incluida en la definición de la notación Big O. SimplificadoO(c) = O(1)

Bueno, por supuesto, podrías escribir Theta (c) (u O (c)), pero ¿por qué eso difiere de Theta (n)? n es solo una variable que denota el tamaño de la entrada. Podría escribir "La función es Theta (c) donde c es una constante". El apéndice importante es ... donde c es una constante . Debe indicar explícitamente que un identificador no es una variable.

Considere la teoría de grafos donde los límites para un algoritmo a menudo se describen como una función de | V | y | E |, o el nodo y el recuento de bordes, respectivamente. Entonces podría ser prudente decir "La función es Theta (| V | * | E | ^ 2)".

Sin embargo, Theta (1) es siempre una constante, suponiendo prácticas matemáticas normales.

La notación theta trata sobre el crecimiento en función de alguna variable, típicamente n. Si fuera necesario aclarar qué variable se pretende, la forma de escribirla sería Theta (n ^ 0). A partir de ahí, es un simple paso aplicar la identidad n ^ 0 = 1 (para n! = 0).

O ( c ) significa específicamente que la clase de algoritmos asociada crece linealmente con c , donde c es el tamaño de una entrada al algoritmo o un parámetro al algoritmo . No es la misma c que se usa para explicar la notación O, porque esa c solo es relevante para la explicación, no para el uso. O ( c ) contiene una c diferente que debe provenir del contexto de entrada del algoritmo.