Hice una pregunta (semilla) sobre sumas de términos de Landau antes , tratando de evaluar los peligros del abuso de la notación asintótica en aritmética, con un éxito mixto. Ahora, aquí nuestro gurú de la recurrencia JeffE hace esencialmente esto: ∑i = 1norteΘ ( 1yo) =Θ(...
Supongamos que un algoritmo tiene una relación de recurrencia en tiempo de ejecución: T(n)={g(n)+T(n−1)+T(⌊δn⌋)f(n):n≥n0:n<n0T(n)={g(n)+T(n−1)+T(⌊δn⌋):n≥n0f(n):n<n0 T(n) = \left\{ \begin{array}{lr} g(n)+T(n-1) + T(\lfloor\delta n\rfloor ) & : n \ge n_0\\ f(n) & : n < n_0 \end{array}...
La notación Big-O oculta factores constantes, por lo que existen algunos algoritmos que no son factibles para cualquier tamaño de entrada razonable porque el coeficiente en el término n es muy grande.O(n)O(norte)O(n)nnorten ¿Hay algún algoritmo conocido cuyo tiempo de ejecución sea pero con algún...
En un video de recitación para MIT OCW 6.006 a las 43:30, Dada una matriz matriz con columnas y filas, el algoritmo de búsqueda de picos 2D, donde un pico es cualquier valor mayor o igual a sus vecinos adyacentes, se describió como:A m nm×nm×nm \times nAAAmmmnnn Nota: Si hay confusión al...
Quiero demostrar que la complejidad temporal de un algoritmo es poliglogarítmica en la escala de entrada. La relación de recurrencia de este algoritmo es , donde .T(2n)≤T(n)+T(na)T(2n)≤T(n)+T(na)T(2n) \leq T(n) + T(n^a)a∈(0,1)a∈(0,1)a\in(0,1) Parece que para algunos depende de . Pero no puedo...
Digamos que tengo un gráficocon aristas. Quiero ejecutar BFS en que tiene un tiempo de ejecución de .El | G |El |solEl ||G|El | miEl | =O(V2)El |miEl |=O(V2)|E|=O(V^2)solsolGO ( V+ E)O(V+mi)O(V+E) Se siente natural escribir que el tiempo de ejecución en este gráfico sería y luego simplificar a .O...
Cerrada . Esta pregunta necesita estar más centrada . Actualmente no está aceptando respuestas. ¿Quieres mejorar esta pregunta? Actualice la pregunta para que se centre en un problema solo editando esta publicación . Cerrado hace 6 años . Wiki tiene...
Esta pregunta es bastante específica en la forma de los pasos tomados para resolver el problema. Dado prueba que .T(n)=2T(2n/3)+O(n)T(n)=2T(2n/3)+O(n)T(n)=2T(2n/3)+O(n)T(n)=O(n2)T(n)=O(n2)T(n)=O(n^2) Entonces los pasos fueron los siguientes. Queremos demostrar que .T(n)≤cn2T(n)≤cn2T(n) \le...
3n=2O(n)3n=2O(n)3^n = 2^{O(n)} es aparentemente cierto. Sin embargo, pensé que era falso porque crece más rápido que cualquier función exponencial con una base de 2.3n3n3^n ¿Cómo es verdadero ?3n=2O(n)3n=2O(n)3^n =
Tengo un problema de tarea que me deja perplejo porque las matemáticas están más allá de lo que he hecho, aunque nos dijeron que no era necesario resolver esto matemáticamente. Solo proporcione un límite superior cercano y justifíquelo. Sea Proporcione un límite superior asintótico en como...
En CLRS (en las páginas 49-50), ¿cuál es el significado de la siguiente declaración: Σni=1O(i)Σi=1nO(i)\Sigma_{i=1}^{n} O(i) es solo una función anónima (de ), pero no es lo mismo que , que realmente no tiene una interpretación
Me pregunto si hay funciones útiles asintóticamente mayores que una función pollogarítmica y menores que una función polinómica. Es decir, una función F( n )f(n)f(n) tal que f(n)=ω(log(n)k)f(n)=ω(log(n)k)f(n) = \omega(\log(n)^k) por alguna constante k>0k>0k > 0 y f(n)=o(nk)f(n)=o(nk)f(n)...
Estoy aprendiendo sobre el análisis asintótico, y he visto algunas complejidades de aspecto exótico que viven entre otras comunes. Por ejemplo, "log log n" está estrictamente entre 1 y log n. Me hace preguntarme si uno siempre puede encontrar complejidades entre otros dos. Específicamente, para...
Aquí hay cuatro principios que no puedo conciliar: Los algoritmos de tiempo exponencial doble se ejecutan enO (22nortek)O(22nk)O(2^{2^{n^k}}) tiempo con k ∈ Nk∈Nk \in \mathbb{N} constante Los algoritmos de tiempo exponencial se ejecutan enO (2nortek)O(2nk)O(2^{n^k}) con k ∈ Nk∈Nk \in \mathbb{N}...