证明了函数的时间复杂度为O(n^3)
证明了函数的时间复杂度为O(n^3)
提问于 2020-10-12 02:52:54
public void function2(long input) {
long s = 0;
for (long i = 1; i < input * input; i++){
for(long j = 1; j < i * i; j++){
s++;
}
}
} 我很确定这个函数的时间复杂度是n^3，但是如果有人能提供一个逐行的解释，那就太好了。
回答 1
Stack Overflow用户
发布于 2020-10-12 21:09:59
首先，如果你写了像O(n^3)这样的东西，你需要定义什么是n，否则它就没有任何意义。假设n是input的值(而不是比特长度)，所以是n = input。
外部循环有k迭代，其中k = n^2。内部循环有1^2，2^2，3^2，...直到k^2次迭代，所以把你得到的所有O(k^3)次迭代加起来(因为第一个m整数的p-th幂的和总是O(m^(p+1)))。
因此，总体时间复杂度为O(n^6)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/64307873
复制相关文章
相似问题
腾讯云开发者
