[时间复杂度]为什么采用二叉排序树查找的平均查找长度为O(log2n)

向右看齐 2022-03-12 13:16 111阅读 0赞

\#\#\#二分法求数值x的整数n次幂

有没有O(log n)的方法呢？得二分思想了。这里的二分是指减少乘法的次数，把重复的运算省去。我要求x的n次方，那么先求x的n/2次方，然后两个相乘起来。如此递归下去。

参考 剑指offer16题 110页

\#\#\#切波那契Fibonacci数列的时间复杂度O(logn)

转自 [https://blog.csdn.net/weixin\_40123831/article/details/80398996][https_blog.csdn.net_weixin_40123831_article_details_80398996]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70][]

<table> 
 <tbody> 
  <tr> 
   <td>// 二分查找<br> //<br> //时间复杂度： log2（N） == lg（N）（最差情况）<br> int BinarySearch(int* array, int size, int data)<br> { <br> &nbsp;&nbsp; &nbsp;int left = 0;<br> &nbsp;&nbsp; &nbsp;int right = size - 1;<br> &nbsp;<br> &nbsp;&nbsp; &nbsp;int mid = left + ((right - left) &gt;&gt; 1);<br> &nbsp;<br> &nbsp;&nbsp; &nbsp;while (left &lt;= right) //表示左闭右闭区间，可以取到边界数值; &nbsp;如果left&lt;right,表示左闭右开区间<br> &nbsp;&nbsp; &nbsp;{ <br> &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if (data == array[mid])<br> &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;{ <br> &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return &nbsp;mid;<br> &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}<br> &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;else if (data &lt; array[mid])<br> &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;{ <br> &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;right = mid - 1;//右边界改变很重要<br> &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}&nbsp;<br> &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;else<br> &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;left = mid + 1;<br> &nbsp;&nbsp; &nbsp;}<br> &nbsp;&nbsp; &nbsp;return -1;<br> }</td> 
  </tr> 
 </tbody> 
</table>

参考  [https://blog.csdn.net/beautyofmath/article/details/48184331][https_blog.csdn.net_beautyofmath_article_details_48184331]

[https://blog.csdn.net/qq\_37703616/article/details/82120258][https_blog.csdn.net_qq_37703616_article_details_82120258]

[http://emb.hqyj.com/Column/Column365.htm][http_emb.hqyj.com_Column_Column365.htm]

\#\#\#二叉排序树查找的平均查找长度为O(log2n)

`推导过程如下:`

`假设有一颗二叉排序树, 总结点数是n, 高度是h, 根结点的高度是1,`

`假设也是满二叉树, n与h的关系, 有公式: n = (2^h) - 1 `

`也就是: h = log2(n+1)`

`对于高度为2,总结点数是3的二叉排序树(满二叉树),查找成功的平均查找长度为:`

`ASL = (1*1 + 2*2) / 3`

`对于高度为3,总结点数是7的二叉排序树(满二叉树),查找成功的平均查找长度为:`

`ASL = (1*1 + 2*2 + 3*4) / 7`

`对于高度为h,总结点数是n的二叉排序树(满二叉树),查找成功的平均查找长度为:`

`ASL = ( 1*1 + 2*2 + 3*4 + ... + h*2^(h-1) ) / n   [等式1]`

`对于[等式1]里的1*1 + 2*2 + 3*4 + ... + h*2^(h-1)`

`该数列有h项: 1*2^0, 2*2^1, 3*2^2, ... , h*2^(h-1)`

`其总和S = 1*2^0 + 2*2^1 + 3*2^2 + ... + h*2^(h-1)  [等式2]`

`等式两边同乘以2,有: 2*S = 1*2^1 + 2*2^2 + 3*2^3 + ... + (h-1)*2^(h-1) + h*2^h  [等式3]`

`用[等式3]减去[等式2]有:`

`S = h*2^h - (2^0 + 2^1 + 2^2 + 2^3 + ... + 2(h-1)) [等式4]`

`其中(2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(h-1))是等比数列求和,设:`

`  ``M = (2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(h-1))`

`等式两边同乘以2,有: 2*M = (2^1 + 2^2 + 2^3 + ... + 2^h)`

`两个等式相减,有: M = 2^h - 1`

`将M代入[等式4]有: S = h * 2^h - (2^h - 1) = (h-1) * 2^h + 1  [等式5]`

`因为 h = log2(n+1),将h代入[等式5],有:`

`S = [ log2(n+1) - 1 ] * 2^[log2(n+1)] + 1`

`  ``= [ log2(n+1) - 1 ] * (n+1) + 1`

`  ``= (n+1) * log2(n+1) - n`

`也就是 S = ( 1*1 + 2*2 + 3*4 + ... + h*2^(h-1) ) = (n+1) * log2(n+1) - n`

`将上述S代入[等式1],有: ASL = [(n+1) * log2(n+1) - n] / n`

`                          ``= [(n+1)/n] * log2(n+1) - 1`

`所以,二叉排序树查找成功的平均查找长度为: `

`ASL = [(n+1)/n] * log2(n+1) - 1   [公式1]`

`其时间复杂度是: O(log2(n))`

参考 [https://blog.csdn.net/Walden1999/article/details/83659874][https_blog.csdn.net_Walden1999_article_details_83659874]

\[代码\]二叉排序树平均检索长度(ASL)的定义在这里不再赘述，在这里其计算方法就是：第一层元素个数 \*1 + 第二层元素个数 \*2 + 第三层元素个数 \*3+……+第n层元素个数 \*n 。

时间复杂度的题1

![20190308092212863.png][]

![20190308092318433.png][]

[https_blog.csdn.net_weixin_40123831_article_details_80398996]: https://blog.csdn.net/weixin_40123831/article/details/80398996
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTU5Mzk4NQ_size_16_color_FFFFFF_t_70]: /images/20220312/a534380425814500bc75d0eedfe9d828.png
[https_blog.csdn.net_beautyofmath_article_details_48184331]: https://blog.csdn.net/beautyofmath/article/details/48184331
[https_blog.csdn.net_qq_37703616_article_details_82120258]: https://blog.csdn.net/qq_37703616/article/details/82120258
[http_emb.hqyj.com_Column_Column365.htm]: http://emb.hqyj.com/Column/Column365.htm
[https_blog.csdn.net_Walden1999_article_details_83659874]: https://blog.csdn.net/Walden1999/article/details/83659874
[20190308092212863.png]: /images/20220312/4a5539f1d5954d64b978816dc18a17d8.png
[20190308092318433.png]: /images/20220312/72db2f2b8ae94b19b1b89d0d91e5ee62.png