Definitivamente no, ya que hacer eso requeriría NO mirar ciertos elementos. Y si su algoritmo no mira cada elemento en este caso, es fácil construir una entrada donde fallaría.
Editar:
Existe la posibilidad de hacer un algoritmo, que funcione mejor en caso de que m << ny también tenga complejidad O (m + n) cuando myn tienen una magnitud similar.
- ¿Qué clases de problemas no se pueden resolver con métodos de optimización?
- Binario (sistema de números): ¿Qué sucede si un byte tiene 16 bits en lugar de 8?
- ¿Qué tan difíciles son las funciones de una variable compleja?
- ¿Cuántos bits aleatorios se necesitan para generar un entero uniformemente aleatorio entre 0 y 9?
- Puedo tomar la teoría de grafos o la combinatoria el próximo semestre. Me interesa la informática teórica. ¿Cuál sería mejor?
Comience con el primer elemento del árbol más pequeño y encuéntrelo en un árbol más grande.
Luego, para cada elemento siguiente, comienza a buscarlo desde una posición anterior en un árbol más grande. Está haciendo un recorrido en orden del árbol más grande, pero en algunos casos va directamente al elemento padre, lo que ahorra tiempo. Más específicamente, si está insertando el nodo X desde un árbol más pequeño y comienza en el nodo Y en un árbol más grande, puede ir hacia arriba o hacia la derecha. Miras a Y padre Z y vas a la derecha solo si X <Z.
El recorrido “en orden” garantiza que no exceda el tiempo O (n + m).
Y tampoco realiza más de dos veces el número de pasos si simplemente estaba insertando elementos ingenuamente en el árbol, que son pasos O (m log (n + m)), por lo que obtiene lo mejor de ambos mundos.
