Análisis asintóticos del espacio necesario para ejecutar algoritmos.
Sabemos que st-non-connectivityst-non-connectivityst\text{-}non\text{-}connectivity está en NLNL\mathsf{NL} según el teorema del teorema de Immerman – Szelepcsényi y dado que st-connectivityst-connectivityst\text{-}connectivity es NL-hardNL-hard\mathsf{NL\text{-}hard} por lo tanto es un espacio...
Aquí hay un problema bien conocido. Dada una matriz de enteros positivos, genera el entero positivo más pequeño que no esté en la matriz.A[1…n]A[1…n]A[1\dots n] El problema se puede resolver en el espacio y el tiempo : lea la matriz, realice un seguimiento en el espacio O ( n ) si 1 , 2 , … , n...
¿Hay algún algoritmo conocido para problemas formulados que requiera una complejidad ESPACIO de O (sqrt (N))? Sé que existen algoritmos con esa gran complejidad de
Dadas dos cadenas, ¿cómo puede verificar si son una permutación entre sí utilizando el espacio O (1)? No se permite modificar las cadenas de ninguna manera. Nota: O (1) espacio en relación con la longitud de la cadena Y el tamaño del
Existe un algoritmo bien conocido de selección de peor de los casos para encontrar el elemento más grande 'ésimo en una matriz de enteros. Se utiliza un medio-de-medianas enfoque para encontrar un buen pivote suficiente, particiones la matriz de entrada en su lugar y luego continúa de forma...
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...
Existen estructuras de datos eficientes para representar particiones establecidas. Estas estructuras de datos tienen buenas complejidades de tiempo para operaciones como Union y Find, pero no son particularmente eficientes en cuanto al espacio. ¿Cuál es una forma de espacio eficiente para...
Tengo el siguiente problema algorítmico: Determine el espacio Turing complejidad de reconocer cadenas de ADN que son palíndromos de Watson-Crick. Los palíndromos de Watson-Crick son cuerdas cuyo complemento invertido es la cuerda original. El complemento se define en forma de letra, inspirado...
He estado estudiando el coeficiente de correlación de rango de Spearman .ρ = ∑yo( xyo- x¯) ( yyo- y¯)∑yo( xyo- x¯)2∑yo( yyo- y¯)2-------------------√ρ=∑i(xi−x¯)(yi−y¯)∑i(xi−x¯)2∑i(yi−y¯)2\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2...
Se ha demostrado que el problema de decidir si una entrada es un palíndromo o no requiere espacio en una máquina Turing. Sin embargo, incluso almacenar la entrada ocupa espacio ¿no significa eso que todas las máquinas de Turing requieren espacio ?Ω ( logn )Ω(Iniciar sesiónnorte)\Omega(\log...
En realidad, descubrí que el conjunto de lenguajes sensibles al contexto, ( \ mathbf {= NSPACE (O (n)) = LBA} idiomas aceptados) no se discuten tan ampliamente como \ mathbf {REG} (idiomas regulares) o \ mathbf {CFL} (lenguajes sin contexto). Y también el problema abierto \ mathbf {DSPACE (O (n))}...
Como dice la pregunta, ¿cómo demostramos que ?NTIME(f(n))⊆DSPACE(f(n))NTIME(f(n))⊆DSPACE(f(n))\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n)) ¿Alguien puede señalarme una prueba o resumirla aquí?
Estoy buscando la implementación del tipo de datos establecido. Es decir, tenemos que mantener un subconjunto dinámico (de tamaño ) del universo de tamaño u connSSSnortennuU= { 0 , 1 , 2 , 3 , ... , u - 1 }U={0,1,2,3,…,u–1}U = \{0, 1, 2, 3, \dots , u – 1\}tuuu operaciones insert(x)(agregue un...
En la década de 1950 se inventaron varios métodos para la minimización de circuitos para funciones booleanas . ¿Existe una extensión de esos métodos o algo similar para optimizar el tiempo o la complejidad espacial de los algoritmos? Por ejemplo, una implementación de clasificación de burbujas...
Considere el siguiente problema: Deje ser una constante. Se nos da una matriz -ary de y 's. Deje .kkkkkkUNAre1× … ×rekAd1×…×dkA_{d_1\times\ldots\times d_k}0 000111norte=∏ki = 1reyoN=∏i=1kdiN = \prod_{i=1}^k d_i Queremos crear una estructura de datos preprocesando para realizar el siguiente tipo...
Cuando se afirma el famoso teorema de Savitch, a menudo se ve el requisito de que sea espacialmente construible (curiosamente, se omite en Wikipedia). Mi simple pregunta es: ¿Por qué necesitamos esto? Entiendo el requisito de que esté en , lo que queda claro en la prueba. Pero ninguna prueba que...