#1 03. 06. 2019 21:51 — Editoval žabí hněv (03. 06. 2019 21:57)
Složitost - Binární vyhledávací strom
Ahoj všem,
řeším úlohu :
Do prázdného binárního vyhledávacího stromu bylo přidáno 1000 prvků. Předpokládejte, že do BVS jsou vkládána náhodná neopakující se čísla. V tomto stavu byly změřeny doby potřebné pro provedení následujících operací:
Přidání prvku - 8ms.
Odebrání prvku - 9ms.
Zjištění maxima ve stromu -10ms.
Vypsání celého stromu - 400ms.
Následně byly přidávány další prvky, až jejich počet dosáhl 1 000 000. Odhadněte dobu potřebnou pro provedení operací v BVS v tomto stavu
Přidání prvku - ?
Odebrání prvku - ?
Zjištění maxima ve stromu - ?
Vypsání celého stromu - ?
-------------------
Takže uvažuji, že průměrná složitost přidání, odebírání je O(n) =log(n). Podle mě i hledání maxima, jelikož jdu pouze po pravé větvi.
Se složitostí vypsání celého stromu to zřejmě bude O(n).
Jak tedy postupovat?
Přidání :
Napadá mě toto:
Spočtu dobu přidání 1000 prvků : T(1000) = log(1000)*8 = 24ms
Spočtu dobu přidání 1000 0000 prvků : T(1000 000) = log(1000 000)*8 = 48ms
Doba po přidání dalších 999 000 prvků na 1000 000 prvků je 48-24 =24ms?
Vypsání všech :
400ms = 1000*t ... t doba vypsani jednoho prvku
t= 0,4ms
Takže doba vypsání 1000 000 prvků je 400 000ms ? děkuji
Offline