Časová zložitosť binárneho vyhľadávania v mierne nevyváženom binárnom strome - dátové štruktúry, časová zložitosť, veľké-o, binárne-vyhľadávacie stromy

Najlepšia doba na spustenie binárneho vyhľadávania jeO (log (n)), ak je binárny strom vyvážený. Najhorší prípad by bol, ak je binárny strom tak nevyvážený, že v podstate predstavuje prepojený zoznam. V takom prípade by doba behu binárneho vyhľadávania bola O (n).

Avšak, ak strom je len mierne nevyvážený, ako je tomu v prípade tohto stromu:

Najlepší prípad by bol ešte O (log n), ak sa nemýlim. Ale čo by bol najhorší prípad?

odpovede:

V zoraďovanom poli n hodnoty, doba spustenia binárneho vyhľadávania hodnoty je O(log n), v v najhoršom prípade.
V najlepší prípad, prvok, ktorý hľadáte, je v presne uprostred, a môže skončiť v neustálom čase.
V priemerný prípad takisto je čas spustenia O(log n).

Typicky, keď hovoríme niečo ako "náklady na hľadanie prvku vo vyváženom binárnom vyhľadávacom strome je O (log n)," to, čo myslíme, je "v najhoršom prípade, musíme robiť O (log n) prácu v priebehuuskutočňovať vyhľadávanie na vyváženom binárnom vyhľadávacom strome. "A keďže tu hovoríme o zápisu veľkého písmena O, má sa predchádzať predchádzajúce vyhlásenie vyvážené stromy vo všeobecnosti namiesto konkrétneho konkrétneho stromu.

Ak máte na mysli určitý BST, môžete pracovaťmaximálny počet porovnaní potrebných na nájdenie akéhokoľvek prvku. Stačí nájsť najhlbší uzol v strome a potom si predstavte, že hľadáte hodnotu, ktorá je väčšia ako táto hodnota, ale je menšia než ďalšia hodnota v strome. To spôsobí, že sa dostanete celú cestu po strome tak hlboko, ako je to možné. maximálny možný počet porovnaní (konkrétne h + 1 z nich, kde h je výška stromu).

Aby ste mohli hovoriť o veľkých nákladoch na vyhľadávanie v strome, potrebujete hovoriť o a rodina stromov rôzneho počtu uzlov. Mohli by ste si predstaviť "trochu vyvážené" stromy, ktorých hĺbka je Θ (√n), napríklad, kde vyhľadávanie by trvalo napríklad čas O (√n). Je však nezvyčajné stretávať sa s týmito stromami v praxi, pretože vo všeobecnosti buď máte (1) úplne nevyvážený strom, alebo (2) používate nejaký vyvážený strom, ktorý by zabránil tomu, aby výška vzrástla tak vysoko.