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

浏览：71日期：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. c++ - 在main函数执行之前段错误，gdb无法调试，估计和g++编译参数相关。2. CentOS7 启动docker.service失败3. 1LL在C++中是什么意思？4. c++ - extern int a=1为什么在函数内部报错？5. c++ - cocos3.8 打包安卓时报错各位大大求围观6. c++ - 保存变量的地址7. c++ 公有继承中，私有成员只能通过基类接口访问，如果我把派生类强制转换为基类，是否能访问其基类私有成员8. c++ - 为何这段数组比较的函数返回值不变？9. c++ - windows操作系统的有些疑惑。10. docker hub 的 URL 设计是什么意思？