大O符号表示简单循环

本文介绍了大O符号表示简单循环的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我只是从一个数据结构课开始，而讲师已经发布了10个问题，并问了其中一个的BigO.根据我已阅读的文章，我假设此代码的大O将为O(1)，因为data参数是单个数据元素.但是，它会根据数字的大小执行多次，因此会使其变为O(N)吗?

I am just starting out in a data structure class, and the instructors have posted 10 problems and asked the Big O of one of them. Based off the posts I have read I am assuming that the Big O of this code would be O(1), since the data parameter is a single data element. However, it does execute multiple times depending on the size of the number so would that make it 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 }

推荐答案

此函数的时间复杂度为 O(log(log(n)).

This function has a time complexity of O(log(log(n)).

i通过乘幂增长成指数增长，因此就是双指数增长"(不确定这是否是一个有效的定义)，而复杂度则是相反的.您可以在此处了解更多信息.

i grows by multiplication in an exponentially growing factor, so that's "double exponential growth" (not sure if that's a valid definition), and the complexity is the inverse. You can read more about this class of complexity here.