Preguntas sobre anotaciones y análisis asintóticos
En la mayoría de las clases de algoritmos introductorios, se introducen anotaciones como (Big O) y , y un estudiante generalmente aprendería a usar una de estas para encontrar la complejidad del tiempo.OOOΘΘ\Theta Sin embargo, hay otras notaciones, como , y . ¿Hay escenarios específicos donde una...
Esta puede ser una pregunta ridícula, pero ¿es posible tener un problema que en realidad se vuelve más fácil a medida que las entradas crecen en tamaño? Dudo que algún problema práctico sea así, pero tal vez podamos inventar un problema degenerado que tenga esta propiedad. Por ejemplo, tal vez...
Esta es una pregunta básica, pero estoy pensando que es lo mismo que , ya que el término más grande debería dominar a medida que avanzamos hasta el infinito. Además, eso sería diferente de O (\ min (m, n)) . ¿Está bien? Sigo viendo esta notación, especialmente cuando discuto algoritmos gráficos....
En "Big O", las anotaciones comunes tienen nombres comunes (en lugar de decir, "Oh, de algún factor constante"): O (1) es "constante" O (log n) es "Logarítmico" O (n) es "Lineal" O (n ^ 2) es "Cuadrático" O (n * log n) es ??? ¿Es solo "n log n" o tiene un nombre especial como el...
Supongamos que tengo una lista de funciones, por ejemplo nloglog(n),2n,n!,n3,nlnn,…nloglog(n),2n,n!,n3,nlnn,…\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots ¿Cómo los ordeno asintóticamente, es decir, después de la relación definida por f≤Og⟺f∈O(g)f≤Og⟺f∈O(g)\qquad f \leq_O g \iff f...
Es bien sabido que este algoritmo 'ingenuo' para barajar una matriz intercambiando cada elemento con otro elegido al azar no funciona correctamente: for (i=0..n-1) swap(A[i], A[random(n)]); Específicamente, dado que en cada una de las iteraciones, se realiza una de las elecciones (con...
Wikipedia, así como otras fuentes que he encontrado, enumeran el voidtipo de C como un tipo de unidad en lugar de un tipo vacío. Esto me parece confuso, ya que me parece que se voidajusta mejor a la definición de un tipo vacío / inferior. No habito valores void, por lo que puedo decir. Una...
Para un lenguaje regular , deje que sea el número de palabras en de longitud . Usando la forma canónica de Jordan (aplicada a la matriz de transición sin anotaciones de algunos DFA para L ), se puede demostrar que para n suficientemente grande , c_n (L) = \ sum_ {i = 1} ^ k P_i (n) \ lambda_i ^...
He escuchado varias veces que para valores suficientemente pequeños de n, O (n) puede considerarse / tratarse como si fuera O (1). Ejemplo : La motivación para hacerlo se basa en la idea incorrecta de que O (1) siempre es mejor que O (lg n), siempre es mejor que O (n). El orden asintótico de...
¿Existe una estructura de datos para mantener una lista ordenada que admita las siguientes operaciones en tiempo amortizado?O ( 1 )O(1)O(1) GetElement (k) : devuelve el elemento de la lista.kkk InsertAfter (x, y) : inserte el nuevo elemento y en la lista inmediatamente después de x. Eliminar (x)...
Si tengo alguna función por su complejidad, el tiempo es O ( mn ), donde m y n son los tamaños de sus dos entradas, tendría que llamar a su complejidad tiempo "lineal" (ya que es lineal en ambos m y n ) o "cuadrática" ( ya que es un producto de dos tamaños) ¿O algo mas? Siento que llamarlo...
Por aquí , Dave Clarke propuso que para comparar el crecimiento asintótico, debe trazar las funciones disponibles. Como científico de la computación teóricamente inclinado, llamo (ed) a este vudú ya que una trama nunca es una prueba. Pensándolo bien, tengo que estar de acuerdo en que este es un...
¿Cuándo se usó Big O por primera vez en informática y cuándo se convirtió en estándar? La página de Wikipedia sobre esto cita a Knuth, Big Omicron y Big Omega y Big Theta , SIGACT de abril a junio de 1976, pero el comienzo de ese artículo dice La mayoría de nosotros nos hemos acostumbrado a la...
El teorema maestro es una herramienta hermosa para resolver ciertos tipos de recurrencias . Sin embargo, a menudo pasamos por alto una parte integral al aplicarlo. Por ejemplo, durante el análisis de Mergesort pasamos felizmente de T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)\qquad T(n) =...
Muchas veces, si las complejidades tienen constantes como 3n, descuidamos esta constante y decimos O (n) y no O (3n). No puedo entender cómo podemos descuidar un cambio tan triple. ¡Algo varía 3 veces más rápido que otro! ¿Por qué descuidamos este hecho?
Actualmente, estoy estudiando Introducción a los algoritmos (CLRS) y hay un método particular que describen en el libro para resolver las relaciones de recurrencia. El siguiente método puede ilustrarse con este ejemplo. Supongamos que tenemos la recurrencia T( n ) = 2 T( n--√) +...
Construya dos funcionesf,g:R+→R+f,g:R+→R+ f,g: R^+ → R^+ satisfying: f,gf,gf, g are continuous; f,gf,gf, g are monotonically increasing; f≠O(g)f≠O(g)f \ne O(g) and g≠O(f)g≠O(f)g \ne
Generalmente se considera que un límite inferior asintótico, como la dureza exponencial, implica que un problema es "inherentemente difícil". Se cree que el cifrado que es "intrínsecamente difícil" de romper es seguro. Sin embargo, un límite inferior asintótico no descarta la posibilidad de que...
Cuando comparamos la complejidad de dos algoritmos, generalmente ocurre que o (posiblemente ambos), donde y son los tiempos de ejecución (por ejemplo) de los dos algoritmos.f(n)=O(g(n))f(n)=O(g(n))f(n) = O(g(n))sol( n ) = O ( f(n))g(n)=O(f(n))g(n) = O(f(n))fffggg Este es siempre el caso? Es decir,...
¿Qué significa log O ( 1 ) nlogO(1)n\log^{O(1)}n ? Soy consciente de la notación big-O, pero esta notación no tiene sentido para mí. Tampoco puedo encontrar nada al respecto, porque no hay forma de que un motor de búsqueda interprete esto correctamente. Para un poco de contexto, la oración donde...