当前位置：网站首页>Prove the time complexity of heap sorting

Prove the time complexity of heap sorting

2022-07-06 12:43:00 【Lemon leaf C】

Time complexity of reactor building

Because the heap is a complete binary tree , A full binary tree is also a complete binary tree . To simplify , Full binary tree will be used to prove .（ Time complexity is an approximation , So more nodes will not affect the final result ）：

Suppose the height of the tree is ：

The first    layer ： Nodes , Need to move down layer
The first layer ： Nodes , Need to move down layer
The first    layer ： Nodes , Need to move down    layer
The first layer ： Nodes , Need to move down    layer
……
The first    layer ： $2^{h-2}$ Nodes , Need to move down layer

The total number of moving steps of the mobile node is ：

$T(n) = 2^0 * (h-1) + 2^1 *(h-2) + 2^2 * (h-3) + 2^3 * (h-4) + ... + 2^{h-3} * 2 + 2^{h-2} * 1$ ①

$2T(n) = 2^1*(h-1)+2^2*(h-2)+2^3*(h-3)+2^4*(h-4)+...+2^{h-2}*2+2^{h-1}*1$ ②

② - ① Dislocation subtraction ：

$T(n) = 1-h+2^1+2^2+2^3+2^4+...+2^{h-2}+2^{h-1}$

$T(n) = 2^0+2^1+2^2+2^3+2^4+...+2^{h-2} + 2^{h-1}-h$

T(n) = 2^h - 1 - h

$n = 2^h-1\, \, \, \, \,\, \, \, \, \, \, h=log_2(n+1)$

$T(n) = n-log_2(n+1) \approx n$

therefore , The time complexity of reactor construction is ${\color{Red} O}({\color{Blue} N})$

版权声明
本文为[Lemon leaf C]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/02/202202131513440490.html

边栏推荐

猜你喜欢

随机推荐