考虑这三个循环
O(N^2)
int i = 0, s = 0;
while (2*i <= N*N) {
s+=i;
i++;
}
O(N)
int i = 0, s = 0;
while (s <= N*N) {
s+=i;
i++;
}
O(平方(N))
int i = 0, s=0, p=1;
while (s < N) {
i++;
p = p*i;
s += i;
}
第一个的时间复杂度是O(N^2)，第二个是O(N)(我觉得N^2更合适)。怎么会？此外，为什么循环 3 是 sqrt(N) 而不是 log(N) - 我如何区分？
最佳答案
对于第二个:
假设迭代将是 k 然后循环将重复:
1+2+3+...k <= N^2 --> k*(k-1)/2 <= N^2 --> k^2 <= N^2 --> k is O(N).
对于第三个:
假设迭代将是 k 然后循环将重复:
1+2+3...+k <= N -->...--> k^2 <= N --> k is O( sqrt(N) ).
关于c - 基本时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40412430/