當前位置:成語大全網 - 新華字典 - 算法導論中,為什麽合並排序的遞歸樹的高度為lgn?

算法導論中,為什麽合並排序的遞歸樹的高度為lgn?

首先計算機科學裏的lgn就是數學上的log2(n)

然後解釋壹下原因:

假設樹的高度為h,觀察前幾層

第壹層:cn(即cn/1),所以該層有1個數

第二層:cn/2,所以該層有2個數

……

最後壹層:c(即cn/n),所以該層有n個數,也是leaves

2^h=n,h=lgn

學工程需要直覺,就不做嚴格的數學分析了

點個贊再走吧~ -..-