Matematické Fórum

parubaa · 13. 06. 2013 10:42

Zdravim, potřeboval bych pomoc se složitostí(nejlepší a nejhorší varianta) b-stromu měl jsem jí odvodit u zkoušky, ale tak nějak jsem na tom pohořel a když si jí teď zkouším doma tak to zas do kupy nedám, mohl by mi prosím někdo pomoc ?

RePRO · 14. 06. 2013 19:17

Zdravím,
u binárního nevyváženého stromu mají operace vyhledávání, vkládání a mazání složitost O(N). U binárního vyváženého stromu mají zmiňované operace složitost O(log(N)).

parubaa · 14. 06. 2013 19:29

čau dík už jsem to našel v nejhorším případě tj. když v kořeni se nachází jen jeden prvek tak ve druhé úrovni bude 2m prvku ve třetí 2m(m+1) ... 2m(m+1)^(k-2) a z toho se pak dostane N= $n=1+2m\sum_{i=0}^{k-2}(m+1)^i$
a pak nejlepší když je všude 2m hodnot tj první 2m druhá 2m(2m+1) ... 2m(2m+1)^(k-1) a z toho pak vyjde $n=2m\sum_{i=0}^{k-1}(2m+1)^i$

Matematické Fórum

#1 13. 06. 2013 10:42

b-strom

#2 14. 06. 2013 19:17

Re: b-strom

#3 14. 06. 2013 19:29

Re: b-strom

Zápatí