以下代码的时间复杂度是多少？
我猜：
for循环以固定时间（即3）运行。函数以n / 3调用自身。因此，“ n”每次收缩3倍，时间复杂度为O（log 3 N）吗？
void function(int n){
if(n == 1)
return 1;
for(int i = 0; i < 3; i++){
cout << "Hello";
}
function(n/3);
}
是的，它是O（log 3 N）。调用循环C完成的工作量。前几个调用将进行：
f(n) = C + f(n/3) = C + C + f(n/9) = C + ... + C + f(1)
C出现的次数是将n除以3等于1的次数，正好是对数3 n。因此，总功为C * log 3 n或O（log 3 N）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句