合并排序递归树的高度 [英] merge sort recursion tree height

问题描述

我正在学习递归树的结构，并试图找出树的高度是n的log b，其中n = 2，其中一个具有10个元素作为输入大小。我正在使用合并排序。

I am learning about recursion tree's and trying to figure out how the height of the tree is log b of n where n = 2 and one has 10 elements as input size. I am working with Merge sort.

完成分割的次数是据我所知树的高度以及树中的层数是高度+1。

The number of times the split is done is the height of the tree as far as I understood, and the number of levels in the tree is height + 1.

但是，如果采用（用于合并排序）log2为10，则得到1，而如果绘制树，则得到的值至少是其2倍。递归发生。

But if you take (for merge sort) log2 of 10 you get 1, where if you draw the tree you get at least 2 times that the recursion occurs.

我哪里出错了？ （我希望我在这里很有道理）

Where have I gone wrong? (I hope I am making sense here)

注意：我正在做自学，这不是家庭作业！

NOTE: I am doing a self study, this is not homework!

推荐答案

log ₂ （10）= 3.321928094887362 ...

log₂(10) = 3.321928094887362...

无论如何，递归调用深度为 O（log（n）），这基本上意味着按照log（n）的顺序。 O（log（n））算法的实际调用深度可能是 k * log（n）+ c ，甚至是 k * log（ n）+ α （n）/ log（log（n））+ c 。

In any case, the recursive call depth is O(log(n)), which basically means "on the order of log(n)". The actual call depth for an O(log(n)) algorithm might be k*log(n)+c, or even k*log(n)+α(n)/log(log(n))+c.

这篇关于合并排序递归树的高度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！