int foo(int n)
{
int sum = 0;
for(int k=1; k <= n; k = k * 2)
{
sum += k;
}
return sum;
}
我有以下功能。 现在，根据我的说法，foo(n) 的运行时复杂度应该是 big-o(logn)。 现在，我被要求找出 foo(n*n*n*n) 的运行时复杂度。应该是什么？ 根据我的说法，它应该只是 big-o(logn)。 我这样说对吗？
最佳答案
它是 O(log n4) → O(4 log n) → O(log n)
关于c - 如何计算这个的复杂性？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25842573/