如何计算Θ（大θ）时间复杂度？求解两个算法复杂度问题

嘿，我来帮你一步步拆解这两个时间复杂度的计算，思路很清晰的：

Q1: for(i=1; i<n; i*=4) sub1(); #

首先先确定这个循环的执行次数：i的取值依次是1, 4, 4², 4³, ...，直到4^k < n。解这个不等式的话，k就是以4为底n的对数，也就是k = log₄n——而对数的底数不影响大Θ的结果，所以循环次数可以简化为Θ(log n)。

接下来，每次循环都会调用一次sub1()，题目明确给出sub1()的时间复杂度是Θ(4ⁿ)（这里的n是整个算法的输入规模，不是循环变量i的值）。把循环次数和单次调用的复杂度相乘，总时间复杂度就是：
Θ(log n * 4ⁿ)

Q2: for(i=1; i<n; i+=4) for(j=1; j<n; j*=4) { sub1(); sub2(); sub1(); sub2(); } #

我们从内到外逐层分析：

1. 内层循环次数：和Q1的循环逻辑完全一致，j每次乘4直到j < n，所以内层循环次数是Θ(log n)。
2. 单次内层循环的耗时：循环体里执行了两次sub1()和两次sub2()。对比两个函数的复杂度：
   • sub1()是Θ(4ⁿ)，属于指数级增长；
   • sub2()是Θ(n⁴ * log n)，属于多项式级增长。
     指数级增长的速度远远快于多项式，所以4ⁿ是绝对的主导项，单次内层循环的总耗时可以简化为Θ(4ⁿ)（两次sub2的耗时相对于它可以忽略不计）。
3. 外层循环次数：i每次加4直到i < n，循环次数大约是n/4，常数因子不影响大Θ结果，所以外层循环次数是Θ(n)。

最后把三者相乘：外层次数 × 内层次数 × 单次内层循环耗时，得到总时间复杂度：
Θ(n * log n * 4ⁿ)

内容的提问来源于stack exchange，提问作者Maengsk