时间戳

首页 > 解决方案 > 这个片段有 O(log^2(n)) 复杂度吗？

java - 这个片段有 O(log^2(n)) 复杂度吗？

问题描述

如果不是，那会是女巫的复杂性吗？谢谢：

    public static int f(int n, int x) {
        for (int i = n; i > 0; i /= 2) {
            for (int j = 0; j < i; j++) {
                x += j; // Assume, this operation costs 1.
            }
        }
        return x;
    }

标签： javafunctionbig-ocomplexity-theory

解决方案

这是一个有趣的。的假设log^2(n)是错误的。亨利很好地减少了荒谬，为什么不能log^2(n)在评论中：

  • 我们可以看到，O(log^2(n)) ⊊ O(n).
  • 内部循环的第一次迭代需要O(n).
  • 因为O(log^2(n)) ⊊ O(n)，假设一定是错误的，因为仅第一次迭代就是∈ O(n).

这也为我们提供了算法的下界：由于算法的第一次迭代是∈ O(n)，那么整个算法至少需要Ω(n)。

现在让我们来估计执行时间。通常，第一种方法是分别估计内环和外环并将它们相乘。显然，外循环具有复杂性log(n)。然而，估计内部循环并非易事。所以我们可以用n（这是一个高估）来估计它并得到n log(n). 这是一个上限。

为了得到更精确的估计，让我们做两个观察：

  1. 内循环基本上将外循环变量的所有值相加i
  2. 循环变量i遵循n, n/2, n/4, ..., 1,的模式0

让我们假设n = 2^k, k ∈ ℕ, k > 0ien是 的幂2。然后n/2= 2^(k-1), n/4 = 2^(k-2), ... 从这个假设推广，如果n不是 的幂2，我们将其设置为 的下一个较小的幂2。事实上，这是一个准确的估计。我将关于为什么的推理留给读者作为练习。

众所周知的事实是2^k + 2^(k-1) + 2^(k-2) + ... + 1 (+ 0) =sum_(i=0)^k 2^i = 2^(k+1) - 1。由于我们的输入是n = 2^k，我们知道这一点2^(k+1)= 2 * 2^k = 2 * n ∈ O(n)。该算法的运行时复杂度实际上是Θ(n)，即这是一个上限和一个下限。它也是一个下限，因为我们所做的估计是准确的。或者，我们可以使用我们对算法存在的观察，∈ Ω(n)从而以这种方式到达Θ(n)。

推荐阅读