c++ - 算法导论里用主方法计算时间复杂度的题

浏览：99日期：2023-03-30

问题描述

递归式如下：T(n)=2T(n/2)+nlgn用主方法求解T(n)。没找到确切答案，所以来看看有没有大神可以解出来的。大家可以再算法导论第三版P95找到这个问题。

问题解答

回答1：

$$a = 2, b = 2, f(n) = nlogn$$$$因为 f(n) ∈ Θ(nlogn), k=1 可以用 case 2$$$$所以 T(n) = Θ(nlog^2n)$$

参考 https://en.wikipedia.org/wiki...

上一条：objective-c - oc, c++混编，c++函数中如何识别self?下一条：c++ - 求解T(n)<T(7n/10)+kn+b

相关文章：
1. javascript - 关于input="file"，重复选择同一文件时不触发change事件的问题2. html5 - 有可以一次性把所有 css外部样式转为html标签内style=" "的方法吗?3. 为什么总是提示我说Template "movieTemplate" not found，我路径都引对了呀4. <tr valign="top"> 看不懂5. type="text/css"是什么意思？6. javascript - type="date"的默认值能改变为当天日期吗7. mysql 使用 join 还是 "," 进行多表查询？？？8. background-image:url(" ")我的图片在桌面9. javascript - 一个字符串转换成数字,例子就是a="2,322.222",b=’1,211.21’,如何在angualr中执行相减10. javascript - body下多出了"1"==$0导致页面上多了1