含O(n)复杂度test1()函数的for循环总时间复杂度求解

首先得指出你给出的循环代码存在逻辑错误：

for(int i=0; i<n;i=i*3){ 
    test1();
}

i的初始值为0，每次循环执行i = i*3后仍然是0，只要n>0，i<n的条件永远成立，循环会无限运行，时间复杂度是无穷大。这应该是笔误，合理推测初始值应为i=1，下面基于这个修正后的情况分析。

循环执行次数分析 #

当i从1开始，每次乘以3，直到i >=n时循环终止。循环执行的次数是满足3^k < n的最大整数k，等价于k = log₃n，所以外层循环的执行次数是O(logn)，这部分你的判断是对的。

总时间复杂度计算 #

已知test1()的时间复杂度为O(n)，这里的n是问题的输入规模（和外层循环的n一致）。每次循环都会调用一次test1()，因此总时间复杂度是循环次数乘以单次调用的时间复杂度：
O(logn) * O(n) = O(nlogn)

不过需要额外说明：如果test1()的时间复杂度是基于循环变量i的规模（比如test1(i)），那情况会不同，但根据题目描述，test1()的时间复杂度明确为O(n)，所以总时间复杂度确实是O(nlogn)。

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