算法计算时间复杂度(1):求递归式 f(n) = 2f(n/2) + n
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法计算时间复杂度(1):求递归式 f(n) = 2f(n/2) + n,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1750字,纯文字阅读大概需要3分钟。
内容图文
当 n = 1 时,f(n) = 1;
当 n > 1 时,f(n) = 2*f(n/2) + n ;
求f(n)的递归式
首先为什么要求递归式呢? 是因为在计算机中有些算法是使用递归方式实现,我们需要计算该递归方式的时间复杂度,来评定算法的优劣。
下面我们来求f(n)的递归式,什么是递归式呢?就是等号左边只有f(n),等号右边只有关于n的表达式。
看到f(n) = 2*f(n/2) + n 这个式子你想到了什么,是不是将f(n/2)变掉。
如何将f(n/2) 变掉呢?
可以假设 n = 2k ,那么 f(n) = f(2k) 然后假设 f(2k) = h(k), f(n/2) = f(k) = h(k/2) 显然这么做毫无意义。
也可以假设 n = 2^k ,那么 f(n) = f(2^k) 然后假设 f(2^k) = h(k), f(n/2) = f(2^(k-1)) = h(k-1)。
那么 f(n) = 2*f(n/2) + n => h(k) = 2*h(k-1) + 2^k ;
另外 n = 1 时,f(n) = 1 ,1 = 2^k => k = 0 时 h(k) = 1 ;
换句话说就是
将
当 n = 1 时,f(n) = 1;
当 n > 1 时,f(n) = 2*f(n/2) + n ;
=>
n = 2^k ;
当 k = 0 时 h(k) = 1 ;
当 k > 0 时 h(k) = 2*h(k-1) + 2^k ;
h(1) = 2*h(0) + 2^1
h(2) = 2*h(1) + 2^2
h(3) = 2*h(2) + 2^3
h(3)= 2*(2*h(1) + 2^2) + 2^3
= 2^2 * h(1) + 2^3 + 2^3
= 2^2 * (2*h(0) + 2^1) + 2^3 + 2^3
= 2^3 * h(0) + 2^3 + 2^3 + 2^3
= 4 * 2^3
h(k) = 2^k * h(0) + k * (2^k)
= (k + 1) * 2^k
我们得到了 h(k) = (k + 1) * 2^k ,因为 n = 2^k => k = log2 n , f(n) = h(k)
f(n) = (log2 n + 1) * 2^log2 n
= (log2 n + 1) * n
= n * log2 n + n
于是得到了 f(n) = n * log2 n + n 。
在得到了递归式之后,时间复杂度 O(nlog2 n)
延伸知识:
求等差数列的前n项和,求等比数列的前n项和
等差数列 A1 = 1,A2 = 2, A3 = 3 …… An = n ; 等差数列 每一项都是前一项加一个常数,这里是1
Sn = A1 + A2 + A3 + …… + An
= 1 + 2 + 3 + …… + n
以下是等差数列的前n项和的推导过程
Sn = 1 + 2 + 3 + …… + n
Sn = n + (n - 1) + (n - 2) + …… + 1
Sn + Sn = (1 + n) + (2 + (n - 1)) + (3 + (n - 2)) + …… + (1 + n)
2 * Sn = n * (n + 1)
Sn = n * (n + 1)/2
等比数列 A1 = 2^1,A2 = 2^2, A3 = 2^3 …… An = 2^n ; 等比数列 每一项都是前一项乘以个常数,这里是2
Sn = A1 + A2 + A3 + …… + An
= 2^1 + 2^2 + 2^3 + …… + 2^n
Sn = 2^1 + 2^2 + 2^3 + …… + 2^n
2 * Sn = 2^2 + 2^3 + …… + 2^n + 2^(n + 1)
2 * Sn - Sn = 2^(n + 1) - 2^1
Sn = (2^(n + 1) - 2^1 ) / (2 - 1)
原文:https://www.cnblogs.com/xiaojun-9/p/14835462.html
内容总结
以上是互联网集市为您收集整理的算法计算时间复杂度(1):求递归式 f(n) = 2f(n/2) + n全部内容,希望文章能够帮你解决算法计算时间复杂度(1):求递归式 f(n) = 2f(n/2) + n所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。