Głębokość drzewa.

[MmadA]

Analizuję algorytm merge sort. W algorytmie tym jako dane wejściowe mamy dany pewien ciąg liczb długości n. Ciąg ten jest dzielony rekurencyjnie na pół do momentu gdy podciąg będzie składał się z pojedyńczego elementu. W wyniku takiego działania dostajemy drzewo o pewnej głębokości. Dla przykładu:



Głębokość takiego drzewa jak mi wiadomo wynosi \(\displaystyle{ log_{2}(n)}\). W jaki sposób wyprowadzić to \(\displaystyle{ log_{2}(n)}\)? Chciałbym policzyć jaka będzie głębokość drzewa gdybym dzielił ten ciąg liczb nie na dwie ale na większą ilość części. Jak się zabrać za takie obliczenia?

PS, jeśli pomyliłem podforum to przepraszam. Nie wiem gdzie bliżej temu problemowi, czy tutaj czy np. do ciągów.

[bartek118]

Logarytm bierze się stąd, że długość tego ciągu dzieli się ciągle przez dwa. Więc wysokość jest równa tyle, ile razy możemy dzielić przez dwa aż do otrzymania jedynki, a to właśnie "definicja" logarytmu. Jakbyś dzielił na \(\displaystyle{ k}\) części, to będzie to \(\displaystyle{ \log_{k} n}\)

[MmadA]

Dzięki za odpowiedź, chyba wszystko jasne.