Autor Tema: Complejidad de los árboles binarios de búsqueda . Inserción y Búsqueda

0 Usuarios y 1 Visitante están viendo este tema.

04 Diciembre, 2024, 04:49 pm
Leído 3171 veces

napolitana

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 23
  • País: es
  • Karma: +0/-0
Hola a todos !!!!!

Tenía na duda acerca de la compejididad que tiene algunas funciones de los ABB , necesito estudiar su complejidad computacional .
La inserción en ABB es  \( O(logn) \) (logarítmica ) en el mejor caso , en cuanto al peor caso  \( O(n) \) (lineal ) . Tengo la duda de si en cuanto vamos a estudiar la complejitud computacional , cúal sería las cotas adecuadas para el caso de inserción .

Por otro lado tengo la duda de si en este caso deba usar  \( O(nlogn) \) dado que cada inserción se cuenta .

Dado un n que es la longitud de un vector aleatorio , su tiempo de ejecución ( insertar valor del vector n en arbol ) en nano-segundos es \( t(n) \) , para calcular la cota subestimada sería  \( t(n)/log(n) \) , la ajustada  \( t(n)/2*log(n) \) y la sobreestimada  \( t(n)/n \) . Los resultados de con varias longitudes de n , son todos valores que va en aumento cuando n aumenta . Nose si está bien si todas los valores tienen que aumentar , lo digo porque en un ejemplo de clase la última columna la cota sobreestimada a medida que la n aumentaba la cota disminuía . Lo que no entiendo es por qué si el peor caso es lineal , los numeros tiende a bajar . Podrían recomendarme algunas cotas que deba usar . La cota ajustada tiene que tender a un valor estable .


Muchas gracias  :D