Aký je najhorší prípad a priemerná zložitosť binárneho vyhľadávacieho stromu?

2024 Autor: Lynn Donovan | [email protected]. Naposledy zmenené: 2023-12-15 23:52

Binárny vyhľadávací strom

Okrem toho, aká je časová zložitosť binárneho vyhľadávacieho stromu v najhoršom prípade?

Rekurzívna štruktúra a BST poskytuje rekurzívny algoritmus. Hľadá sa v BST má O (h) najhoršie - prípad beh programu zložitosť , kde h je výška strom . Keďže s binárny vyhľadávací strom s n uzlami má minimum O (log n) úrovne, trvá to najmenej O (log n) porovnania na nájdenie konkrétneho uzla.

Po druhé, aká je časová zložitosť binárneho vyhľadávania s iteráciou? Výkonnosť Binárny vyhľadávací algoritmus : Preto, časová zložitosť binárneho vyhľadávacieho algoritmu je O(log₂n), čo je veľmi efektívne. Pomocný priestor, ktorý používa, je O(1) pre iteratívny implementácia a O(log₂n) pre rekurzívnu implementáciu kvôli zásobníku hovorov.

Otázkou tiež je, aká by bola najhoršia časová zložitosť vyhľadávania prvku v binárnom vyhľadávacom strome?

Časová zložitosť : The časová zložitosť v najhoršom prípade z Vyhľadávanie a operácie vkladania sú O(h), kde h je výška Binárny vyhľadávací strom . In v najhoršom prípade , my smieť mať do cestovať od koreňa do najhlbší listový uzol. Výška zošikmenia strom môže stať sa n a časová zložitosť z Vyhľadávanie a operáciu vloženia smieť stať sa O(n).

Je Big O najhorším prípadom?

Takže v binárnom vyhľadávaní najlepšie prípad je O (1), priemer a v najhoršom prípade je O (logn). Stručne povedané, neexistuje vzťah typu „ veľké O sa používa na v najhoršom prípade , Theta pre priemer prípad “. Všetky typy zápisov možno použiť (a niekedy aj používajú), keď sa hovorí o najlepšom, priemernom, príp v najhoršom prípade algoritmu.