如何在改变输入大小时找到时间复杂度？
How to find time complexities when varying the input size?
我想知道当 doubling 输入大小时如何计算函数的时间复杂度。我特别指的是著名的 Algorithms Design 练习题。
Example Problem Questions Here
解决办法：
Solutions
起初，看起来他只是将值插入到函数中。 n^3 变为 (2n)^3，因此变为 8n^3，因此 8 times slower。
我开始感到困惑的地方是查看 nlogn 和 2^n。执行此计算时我缺少某种技巧还是只是数学替换？我已经通读了他书中的章节，但似乎找不到解决办法。
只需使用简单的标识：
2nlog(2n) = 2n(logn + log2) = 2nlogn + 2nlog2
2^(2n) = (2^n)^2
似乎很明显哪个答案合适。
我想知道当 doubling 输入大小时如何计算函数的时间复杂度。我特别指的是著名的 Algorithms Design 练习题。
Example Problem Questions Here
解决办法： Solutions
起初，看起来他只是将值插入到函数中。 n^3 变为 (2n)^3，因此变为 8n^3，因此 8 times slower。
我开始感到困惑的地方是查看 nlogn 和 2^n。执行此计算时我缺少某种技巧还是只是数学替换？我已经通读了他书中的章节，但似乎找不到解决办法。
只需使用简单的标识：
2nlog(2n) = 2n(logn + log2) = 2nlogn + 2nlog2
2^(2n) = (2^n)^2
似乎很明显哪个答案合适。