Esta es una pregunta de tarea del libro de Udi Manber. Cualquier pista sería buena :) Debo demostrar que: n ( log3( n ) )5 5= O ( n1,2)n(log3(n))5=O(n1.2)n(\log_3(n))^5 = O(n^{1.2}) Intenté usar el Teorema 3.1 del libro: c > 0 a > 1F( n )C= O ( aF( n ))f(n)c=O(af(n))f(n)^c =...
Desde el punto de vista del comportamiento asintótico, ¿qué se considera un algoritmo "eficiente"? ¿Cuál es el estándar / razón para dibujar la línea en ese punto? Personalmente, pensaría que cualquier cosa que sea ingenuamente llamaría "subpolinomio", de modo que como sería eficiente y cualquier...
¿Qué notación se usa para discutir los coeficientes de las funciones en notación big-O? Tengo dos funciones: f(x)=7x2+4x+2f(x)=7x2+4x+2f(x) = 7x^2 + 4x +2 g(x)=3x2+5x+4g(x)=3x2+5x+4g(x) = 3x^2 + 5x +4 Obviamente, ambas funciones son , de hecho , pero eso no permite una comparación más allá de...
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) =Θ(...
Estoy tratando de entender qué está mal con la siguiente prueba de la siguiente recurrencia T(n)=2T(⌊n2⌋)+nT(n)=2T(⌊n2⌋)+n T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n T(n)≤2(c⌊n2⌋)+n≤cn+n=n(c+1)=O(n)T(n)≤2(c⌊n2⌋)+n≤cn+n=n(c+1)=O(n) T(n) \leq...
Me dieron una tarea con Big O. Estoy atrapado con bucles anidados que dependen del bucle anterior. Aquí hay una versión modificada de mi pregunta de tarea, ya que realmente quiero entenderla: sum = 0; for (i = 0; i < n; i++ for (j = 0; j < i; j++) sum++; La parte que me está sacudiendo...
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 =
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...
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