简单循环的大O符号
简单循环的大O符号
提问于 2016-03-20 11:40:59
我刚开始在一个数据结构课，教师已经张贴了10个问题，并询问其中一个大O。根据我读过的文章，我假设这段代码的大O将是O(1)，因为数据参数是单个数据元素。但是，它确实执行了多次，这取决于数字的大小，所以这会使它成为O(N)吗？
public class Main {
public static void main(String[] args) {
f(100000);
}
public static long f (int n) {
long sum = 0;
for (long i = 2; i < n; i = i * i) {
sum += i;
System.out.println(sum);
}
return sum;
} // end f
}回答 2
Stack Overflow用户
回答已采纳
发布于 2016-03-20 12:14:52
该函数的时间复杂度为O(log(log(n)).。
i以指数增长的倍数增长，所以这就是“双指数增长”(不确定这是否是一个有效的定义)，而复杂性则是相反的。您可以阅读有关这类复杂性这里的更多信息。
Stack Overflow用户
发布于 2016-03-20 13:57:59
使用Sigma符号分析算法
要严格分析算法的增长，可以使用Sigma符号，如下所示：
通过以下方式：
其中我们还假设，在使用(*)的结果的等式中，对于某些正整数j，n不是形式2^(2^j)上的一个数字。对于这个假设不成立的n值，只需在上面的k之和中删除地板功能。
结果:日志记录时间复杂度
从上面可以看出，您的算法具有log-logarithmic时间复杂度，即(渐近上界) O(log(log n))。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/36118592
复制相关文章
点击加载更多
相似问题
反应钩形与脉轮
如何转换/动画与脉轮-UI？
脉轮UI图标
脉轮UI，如何使组件与左边对齐？
脉轮用户界面图标作为变量
腾讯云开发者
