Oszacować średnia złożoność czasowa zbudowania drzewa BST z n losowo
wybranych liczb.
Wykorzystać wzór całkowy sumowania szeregów.
prosze o pomoc
0
1
Studia skończyłem prawie 10 lat temu, ale jakoś tak to szło:
Na logikę powinno wyjść O(NlogN), ponieważ de facto sortujesz te liczby. Zauważ, że wstawienie nowego elementu do BST zajmuje log(h), gdzie h - wysokość drzewa, ponieważ liczby są losowe, to można założyć, że to drzewo będzie w średnim przypadku zbalansowane. Czyli mamy sumę po h od 1 do N z log(h). A taką sumę można sprowadzić do całki oznaczonej: http://matematykadlastudenta.pl/strona/290.html (tutaj był chyba na to jakiś lemat, nie wiem czy dla każdego szeregu tak jest) i wychodzi NlogN plus jakaś stała, czyli O(NlogN).
EDIT: Chyba coś zje**ałem, bo tak liczy się złożoność budowy kopca (heapify), która jest O(N)
0
Tu:
https://aofa.cs.princeton.edu/60trees/
Można coś poczytać.