我只是从一个数据结构课开始,而讲师已经发布了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.
更多推荐
大O符号表示简单循环
发布评论