Si desea aplicar el Teorema maestro, deberá resolver el término n / log (n), esto se explica bien aquí: Teorema maestro: T (n) = 2T (n / 2) + n / log n =? Pensé que la respuesta sería Θ (nlogn), pero la solución dice que el Teorema maestro no se aplica.
Dependiendo de lo apretado que quieras tus asintóticos, pensé en intervenir para darte un enfoque burdo pero simple para manejar esto, aunque no podrás decir que es un límite Big-Theta. De ninguna manera afirmo que este es el límite más estricto posible , pero a menudo encuentro que las personas se vuelven muy estrechas cuando se trata del Master Theorem y su aplicabilidad (tanto de aquellos que abusan de sus condiciones como de aquellos que simplemente lo notan) No aplique directamente, simplemente deténgase). Puede formar una recurrencia diferente que se aplique a ella, luego usar las propiedades de la recurrencia para decir cosas sobre la original. Solo quería usar mi respuesta para mostrarte cómo aún puedes usar el Teorema Maestro para obtener algunos límites.
Primero, [matemáticas] n / log {n} \ en O (n) [/ matemáticas]. Te dejaré convencerte de ese hecho probándolo en tu propio tiempo. Ahora, eso significa que si reescribe la recurrencia como una nueva donde la reemplazamos con el término lineal, obtenemos un límite Big-Oh.
- ¿Es CodeChef la opción correcta para practicar problemas algorítmicos hoy en día?
- ¿El aprendizaje por refuerzo está recibiendo actualmente más atención que los algoritmos genéticos?
- ¿Qué temas en algoritmos modernos no están cubiertos en CLRS?
- Cómo guardar la entrada del usuario dentro de una matriz en Java
- ¿Cuál es el algoritmo más rápido para generar números primos y su complejidad?
Sea [math] T_2 (n) = 2T_2 (n / 2) + n [/ math], donde [math] T (1) = 1 [/ math].
Ahora puede aplicar el teorema maestro a [matemáticas] T_2 (n) [/ matemáticas]. Obtendrá esa [matemática] T_2 (n) \ in \ Theta (n \ log_2 {n}) [/ math].
De esto por las propiedades de las recurrencias [matemáticas] t (n) [/ matemáticas] y [matemáticas] T_2 (n) [/ matemáticas], [matemáticas] t (n) \ en O (n \ log {n}) [/mates].
A continuación, observe que [matemáticas] n / \ sqrt {n} \ en O (n / \ log {n}) [/ matemáticas] y [matemáticas] n / \ sqrt {n} = \ sqrt {n}. [/ matemática] Así que ahora vincularemos desde abajo asintóticamente la recurrencia [math] t (n) [/ math].
Ahora puede formular una nueva recurrencia (nuevamente), [matemática] T_3 (n) = 2 T_3 (n / 2) + \ sqrt {n}. [/ Matemática] Esto también puede aplicarse al Teorema Maestro, y usted obtendrá esa [matemática] T_3 (n) \ in \ Theta (n) [/ matemática].
Por lo tanto, puede concluir que [math] t (n) \ in \ Omega (n) [/ math] y [math] t (n) \ in O (n \ log {n}) [/ math]. Esto significa que el comportamiento asintótico de [math] t (n) [/ math] está entre estos dos.
