Preguntas sobre anotaciones asintóticas como Big-O, Omega, etc.
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...
Estoy leyendo un libro llamado Principios de informática (2008), de Carl Reynolds y Paul Tymann (publicado por Schaum's Outlines). El segundo capítulo presenta algoritmos con un ejemplo de búsqueda secuencial que simplemente itera a través de una lista de nombres y devuelve VERDADERO si se...
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....
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...
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...
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...
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
¿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...
He estado leyendo Introducción a los algoritmos de Cormen et al. y estoy leyendo la declaración del teorema del Maestro que comienza en la página 73 . En el caso 3 también hay una condición de regularidad que debe cumplirse para usar el teorema: ... 3. Si
Entiendo que es más rápido que Θ ( n log n ) y más lento que Θ ( n / log n ) . Lo que me resulta difícil de entender es cómo comparar Θ ( n log n ) y Θ ( n / log n ) con Θ ( n f ) donde 0 < f < 1 .Θ ( n )Θ(n)\Theta(n)Θ ( n logn )Θ(nlogn)\Theta(n\log n)Θ ( n / logn )Θ(n/logn)\Theta(n/\log...
Supongamos que se nos dan dos números y y que queremos encontrar para l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r El algoritmo ingenuo simplemente verifica todos los pares posibles; por ejemplo en ruby tendríamos: def max_xor(l, r) max = 0...
Estoy leyendo un papel, y dice en su descripción complejidad del tiempo que la complejidad es el tiempo .O~( 22 n)O~(22n)\tilde{O}(2^{2n}) He buscado en Internet y Wikipedia, pero no puedo encontrar lo que significa esta tilde en notación big-O / Landau. En el documento en sí tampoco he encontrado...
escribí ∑i=1n1i=∑i=1nO(1)=O(n)∑i=1n1i=∑i=1nO(1)=O(n)\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n) Pero mi amigo dice que esto está mal. De la hoja de trucos de TCS sé que la suma también se llama que tiene un crecimiento logarítmico en n ....
Primero, déjame escribir la definición de grande OOOsolo para hacer las cosas explícitas. f(n)∈O(g(n))⟺∃c,n0>0f(n)∈O(g(n))⟺∃c,n0>0f(n)\in O(g(n))\iff \exists c, n_0\gt 0 tal que0≤f(n)≤cg(n),∀n≥n00≤f(n)≤cg(n),∀n≥n00\le f(n)\le cg(n), \forall n\ge n_0 Digamos que tenemos un número finito de...
Digamos, por ejemplo, que estoy procesando cadenas que requieren un análisis de dos cadenas. No he dado información sobre cuáles podrían ser sus longitudes, por lo que provienen de dos familias distintas. ¿Sería aceptable llamar a la complejidad de un algoritmo u (dependiendo de si usamos un...
Entonces tengo esta pregunta para probar una declaración: O(n)⊂Θ(n)O(n)⊂Θ(n)O(n)\subset\Theta(n) ... No necesito saber cómo demostrarlo, solo que en mi opinión esto no tiene sentido y creo que debería ser ese .Θ(n)⊂O(n)Θ(n)⊂O(n)\Theta(n)\subset O(n) Tengo entendido que es el conjunto de todas...
¿Cómo se define el análisis asintótico (big o, little o, big theta, big theta, etc.) para funciones con múltiples variables? Sé que el artículo de Wikipedia tiene una sección, pero usa mucha notación matemática con la que no estoy familiarizado. También encontré el siguiente documento:...
En el trabajo, se me ha encomendado la tarea de inferir cierta información sobre un lenguaje dinámico. Reescribo secuencias de declaraciones en letexpresiones anidadas , así: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x...