你们能告诉我f3
的时间复杂度是多少吗?
我在想 sqrt(n).log(n) 但官方答案是 n。
有什么想法吗?
#define PARTS 4
void f3(int n) {
if (n < 4)
return;
for (int i = 0; i * i < n; i++)
printf("%d", i);
for (int i = 0; i < PARTS; i++)
f3(n / PARTS);
}
最佳答案
复杂度取决于 printf
的复杂度:如果您可以假设 printf("%d",i)
的成本恒定,那么时间复杂度似乎为为O(N + k.sqrt(N)),其中 k=-1。由于 sqrt(N) 由 N 主导,因此可以简化为 O(N)。
cost(4*N) = 4*cost(N) + sqrt(4*N)
4*N + k*sqrt(4*N) = 4*N + 4*k*sqrt(N) + 2*sqrt(N)
2*k = 4*k+2
k = -1
如果printf("%d",i)
的复杂度为log(i),考虑到转换产生的位数>i
以 10 为基数,整体复杂度更难评估:k.sqrt(N) 变为 k.log(N).sqrt(N),仍然以N为主。
关于c - C语言的简单时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49308723/