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

9

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)?

usuario10326
fuente

Respuestas:

8

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) ...

Halcón
fuente
Ya veo, pero ¿por qué no solo Theta (c) para cubrir cualquier constante? ¿Es solo una convención?
user10326
8
@ user10326: Creo que es porque "c" podría malinterpretarse, claramente tiene que decir que es una constante mientras que "1" hace el mismo trabajo sin ambigüedades.
Falcon
Entonces, ¿el número real es irrelevante? ¿Usamos 1 en lugar de 5 como convención?
user10326
1
@ user10326: Sí, porque no hace la diferencia. Pero me abstendría de usar "0" porque eso podría generar mucha confusión.
Falcon
@ user10326: Falcon su respuesta tenía mucho sentido, ¿no? si fuera 5 en lugar de 1, dejar caer 5 O(5 * n^2)sería menos natural, mientras que caer * 1es matemática básica.
Steven Jeuris
13

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)

Jay Lindquist
fuente
3

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.

Max
fuente
Theta(1) however is always a constant.Esta es la parte que no get.Theta (c) es siempre una constante como well.Right Así que me preguntaba si el? 1Tiene un significado especial
user10326
55
@ user10326: no, cno siempre es una constante, ya que ces una variable si no declaras explícitamente que debería interpretarse como una constante ... que es exactamente la sutil diferencia que se evita 1.
blubb
Ok, pero representa un tiempo constante.
user10326
2
@ user10326: No, no, no representa un tiempo constante. Representa el tiempo que crece linealmente con c. Esos son diferentes , porque necesitas algo adicional para forzar que el valor de c nunca cambie, mientras que 1 nunca cambia.
jprete
1
@ user10326: O, dicho de manera más simple: cno es una constante; ces una carta Otras letras representan variables, ¿cómo espera que el lector sepa que esta tampoco?
Random832
0

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).

Peter Taylor
fuente
Pero, ¿por qué dices n^0denotar tiempo constante y no n^1en tu ejemplo?
user10326
@ user10326, porque n ^ 1 = n no es constante. Crece linealmente.
Peter Taylor
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.

jprete
fuente