Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 03. 06. 2019 21:51 — Editoval žabí hněv (03. 06. 2019 21:57)

žabí hněv
Příspěvky: 61
Reputace:   
 

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

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson