此功能的增长顺序是什么?

用户名

我是算法新手,也是0。这个函数的增长顺序是什么?

我做一个println并且f(10)运行15次。f(20)运行31次。

在我看来log(N)*N/2是这样logarithmic还是linearithmic

   static long f (long N) {
        long sum = 0;
        for (long i = 1; i < N; i *= 2)
            for (long j = 0; j < i; j++)
                sum++;
        return sum;
    }
templatetypedef

运行时间为O(n)。看到这一点,请注意,内循环运行1次在第一次循环,2次上的下一次迭代,在下一迭代4次,更通常为2的2倍次迭代。外循环在lg n次迭代后停止,因为它不断加倍,因此总工作量为

1 + 2 + 4 + 8 + ... + 2 lg n

这是一个几何级数总和,得出2 lg n + 1-1 = 2·2 lg n -1 = 2n-1 = O(n)。

希望这可以帮助!

本文收集自互联网,转载请注明来源。

如有侵权,请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

什么是增长顺序?您如何计算?

来自分类Dev

算法的增长顺序

来自分类Dev

循环的增长顺序

来自分类Dev

N的增长顺序

来自分类Dev

以下代码片段的最坏情况运行时间随N的增长顺序是什么?

来自分类Dev

分析最坏情况的增长顺序

来自分类Dev

根据增长顺序对断言进行排序?

来自分类Dev

为什么优先选择增长顺序作为运行时算法性能的基准?

来自分类Dev

MySQL增长变化和增长顺序的总和

来自分类Dev

估计算法运行时间的增长顺序

来自分类Dev

增长顺序-嵌套循环,索引加倍的外部循环

来自分类Dev

SICP-练习2.63-确定增长顺序

来自分类Dev

为什么自上而下的堆构建方法比自下而上的堆效率低,即使其增长顺序比O(n)低O(log n)?

来自分类Dev

此递归函数的运算顺序是什么?

来自分类Dev

找到一个调用许多过程的过程的增长顺序

来自分类Dev

从运行时间和变化率估计算法的增长顺序

来自分类Dev

循环最坏情况下运行时间的增长顺序

来自分类Dev

此功能的实际用例是什么?

来自分类Dev

此功能的最终参数是什么?

来自分类Dev

是什么使此功能运行慢得多?

来自分类Dev

此功能的复杂性是什么?

来自分类Dev

此jquery语法的功能是什么?

来自分类Dev

此功能的O标记将是什么?

来自分类Dev

此功能背后的机制是什么?

来自分类Dev

此功能定义的意义是什么?

来自分类Dev

此功能是什么?如何实现?

来自分类Dev

Matlab中的此功能是什么?

来自分类Dev

此功能的实际用例是什么?

来自分类Dev

此功能的作用是什么