Visualice $T(n)=2T(n/2)+O(n)=O(n\log(n))$ en un árbol

Question

Entiendo la demostración matemática de $T(n)=2T(n/2)+O(n)=O(n\log(n))$ Sin embargo, no consigo entender visualmente cómo funciona. Intuitivamente, sólo se siente como debería $O(n^2)$ . ¿Puede mostrarme por qué estas dos corrientes de pensamiento son erróneas?

1. Imagine un árbol binario con $n$ nodos. En cada nodo $O(n)$ es necesario ejecutar la operación. Una función recursiva para esto sería por tanto $T(n)=O(n)+T(\text{left})+T(\text{right})=2T(n/2)+O(n)$ . Dado que existen $n$ nodos y la operación es $O(n)$ tiempo para hacerlo $T(n)=nO(n)=O(n^2)$ .
2. Si se tomara este árbol binario y se simplificara la operación para que fuera $O(1)$ la complejidad de este nuevo árbol sería $T(n)/O(n)=O(n\log(n))/O(n)=O(\log(n))$ (ya que ahora las cosas son menos complejas por un factor de $O(n)$ ). Sin embargo, se ha demostrado matemáticamente que $T(n)=2T(n/2)+O(1)=O(n)$ no $O(\log(n))$ .

Nota: Entiendo la prueba matemática de por qué $T(n)=2T(n/2)+O(n)=O(n\log(n))$ obras. Sin embargo, no puedo visualizarlo ni captarlo intuitivamente.

Answer 1

Creo que estás malinterpretando lo que el teorema maestro describe. La tarea aquí es procesar un árbol, que no es exactamente lo mismo que sólo procesar los nodos. Perdón por el juego de palabras, pero es como si te faltara el árbol en el bosque detrás de los nodos. :-)

En cada nodo $O(n)$ es necesario ejecutar la operación.

Eso es incorrecto - exactamente porque la tarea real es procesar un árbol, no sólo nodos individuales de uno en uno. Por eso el número de operaciones es NO el mismo en diferentes nodos. Por ejemplo, simplemente por la definición de la función $T$ el nodo superior requiere $T(n)$ porque es la raíz de un árbol de tamaño $n$ que necesitamos procesar; pero cada hoja, al ser un árbol con un solo nodo, sólo requiere $T(1)$ que es una constante.

Dado que existen $n$ nodos y la operación es $O(n)$ tiempo para hacerlo $T(n)=nO(n)=O(n^2)$ .

Incorrecto, como ya se ha explicado: cada nodo requiere un tiempo diferente.

Si se tomara este árbol binario y se simplificara la operación para que fuera $O(1)$ ,

Es lo mismo.

la complejidad para este nuevo árbol sería $T(n)/O(n)=O(n\log(n))/O(n)=O(\log(n))$

Lo siento, pero esto no tiene ningún sentido. Usted comenzó este cálculo con el supuesto que $T(n)=O(n\log(n))$ , ya que eso es lo que reemplazó $T(n)$ con. Incluso dejemos a un lado la cuestión de por qué supones eso desde el principio si es lo que intentamos deducir (aunque sea un grave error lógico). Pero si ya se sabe lo que $T(n)$ es, ¿qué sentido tiene "deducir" algo diferente para él?

---

Lo que el teorema maestro describe es la divide y vencerás enfoque. Tu principal idea errónea es que en cada nodo ocurre algo igual, pero eso no es cierto. De hecho, hay tres cosas que suceden en cada nodo (para un árbol binario):

1. Necesitamos procesar el subárbol izquierdo, con un coste de $T(\text{left})$ ;
2. Necesitamos procesar el subárbol correcto, con un coste de $T(\text{right})$ ;
3. Y necesitamos algo de tiempo para realizar adicional operaciones en el nodo, como formar subárboles, juntar los resultados de los subárboles, etc.

El " $+O(n)$ "en la fórmula recursiva de su ejemplo se refiere únicamente al coste computacional de la última parte - para un nodo que es la raíz de un (sub)árbol de tamaño $n$ es NO todo el coste de lo que ocurre en un nodo, y es NO el mismo para todos los nodos. El número total de operaciones que tenemos que realizar en un nodo de este tipo se denomina por definición $T(n)$ y de hecho se expresa mediante la relación recursiva $$T(n)=O(n)+T(\text{left})+T(\text{right})=2T(n/2)+O(n).$$