带有随机对象的 while 循环的大 O 时间复杂度

Question

public class Question2 {
          //running time of function is N!!!!!!
    public static boolean isThere(int[] array, int num, int index){
        boolean isItThere = false;   //running time of 1
        for(int i =0; i <= index; i++){      //running time i
            if(array[i] == num){   //running time of 1
                isItThere = true;   //running time of 1
            }
        }
        return isItThere;
    }


    public static int[] firstAlgo(int N){
            Random random = new Random();  //running time of 1(initilizing)k
          int[] arr = new int[N];
          for (int i = 0; i < N; i++){
              int temp = random.nextInt(N+1);  //running time of random is O(1)
              while (isThere(arr, temp, i)){
                  temp = random.nextInt(N+1);
              }
              arr[i] = temp;
          }
         return arr;
    }

}

我想弄清楚while循环的时间复杂度，我知道isThere函数的运行时间是N所以是firstAlgo中的主for循环

Answer 1

你可以根据经验来做。只是运行代码，并用不同的 N 值计时。我这样做了，复杂度似乎是 O(N^2)。我运行进行了一系列测试，每次都将 N 加倍，而且时间似乎从未从大致翻两番后退缩。我厌倦了在 N = 256000 处等待，这花费了大约 200K 毫秒。

如果您想这样做，您需要对更多运行进行更仔细的分析。您可以设置一个外部循环来继续进行批量测试，例如在每个级别进行 10 次测试，对它们进行计时，然后将 N 加倍并再次进行……一直记录。您可以运行一夜之间进行测试，并根据经验对行为有一个非常清晰的认识。

如果这不是您想要的解决方法，它至少可以成为 double-check 您的答案的一种方式。

Answer 2

请记住，Big-O 是最坏的情况。正如其中一条评论中提到的，这有可能永远不会终止导致 Big-O of infinite 因为这段代码是 non-deterministic.

对于随机执行预期的一般情况。您正在查看 isThere 函数的 O(N)。对于最后一次查找值的迭代，您将平均 N 次操作。在这一点上你是 O(N^2)。最后你需要重复这个操作 N 次来填充数组，这将你带到 O(N^3).

Answer 3

简短版本：

预期运行时间为 Θ(N² log N).
我有数学和经验数据来支持这一点。

这是一个图表，将完成的经验工作量与我为 N² log N 形式的函数得到的 best-fit 近似值进行了比较，它是 (N ² ln N) / 1.06:

好奇吗？继续阅读。 :-)

让我们从这里的代码退一步，看看实际的逻辑在做什么。代码的工作原理如下：对于数组 0, 1, 2, 3, ..., N 的每个前缀，代码不断生成运行0 到 N 之间的 dom 数字，直到生成一个未被生成的数字为止以前见过。然后它在当前数组槽中记下该数字并移动到下一个。

我们在此分析中需要的一些观察结果。想象一下，我们即将进入 firstAlgo 中的循环的第 k 次迭代。关于数组前 k 个槽的元素，我们能说些什么？好吧，我们知道以下内容：

0,1,2,3,...,k-1位置的元素都互不相同。这样做的原因是，每个循环迭代只会在发现到那时为止没有出现在数组中的东西时停止。
None 这些值等于 0，因为数组最初填充为 0，如果在上一步中生成 0，则不允许。
由于 (1) 和 (2)，插槽 0、1、2、...、k-1 和 k 中的元素都不同。

现在，我们可以开始进行一些数学运算了。让我们看一下 firstAlgo 中循环的第 k 次迭代。每次我们生成一个运行dom 数字时，我们都会查看 (k+1) 个数组槽以确保该数字不会出现在那里。（顺便说一句，我将使用这个数量作为完成的总工作量的代表，因为大部分能量将用于扫描该阵列。）所以我们需要问 - 根据预期，有多少数字是我们要在找到独特的之前生成吗？

上面列表中的事实 (3) 在这里很有帮助。它表示在第 k 次迭代中，数组中的前 k+1 个槽位彼此不同，我们需要生成一个不同于所有这些槽位的数字。我们可以选择运行dom 数字的 N+1 个选项，因此我们可以选择的数字有 (N+1) - (k+1) = N - k 个选项不会被使用。这意味着我们选择一个尚未出现的数字的概率是 (N - k) / (N + 1).

快速检查以确保此公式正确：当 k = 0 时，我们可以生成除 0 以外的任何运行dom 数字。有 N+1 个选择，所以我们这样做的概率是 N / (N+1)。这符合我们上面的公式。当 k = N-1 时，之前的所有数组元素都不同，我们只能选择一个有效的数字。这意味着我们的成功概率为 1 / (N+1)，再次符合我们的公式。酷！

概率论中有一个有用的事实，如果你继续抛一枚正面朝上概率为 p 的有偏硬币，那么在你抛出正面之前的预期抛掷次数是 1 / p。（更正式地说，that's the mean of a geometric random variable with success probability p，您可以使用期望值的正式定义和一些泰勒级数来证明这一点。）这意味着在该循环的第 k 次迭代中，运行dom 数的期望数在我们得到一个唯一的之前我们需要生成 (N + 1) / (N - k).

总的来说，这意味着在 firstAlgo 中循环的迭代 k 上完成的预期工作量由 (N + 1)(k + 1) / (N - k) 给出。那是因为

预计会生成 (N + 1)/(N - k) 个数字，并且
每个生成的数字需要检查 (k + 1) 个数组槽。

然后我们可以通过将 k = 0 到 N - 1 相加来得到我们完成的总工作量。这给了我们

      0+1          1+1          2+1                 N
(N+1)----- + (N+1)----- + (N+1)----- + ... + (N+1)-----
      N-0          N-1          N-2                 1

现在，我们“所有”要做的就是简化这个求和，看看我们得到了什么。 :-)

让我们从这里分解出常见的 (N + 1) 项开始，回馈

       /  1     2     3           N  \
 (N+1)|  --- + --- + --- + ... + --- |
       \  N    N-1   N-2          1  /

忽略第 (N + 1) 项，我们剩下的任务是简化总和

 1     2     3           N
--- + --- + --- + ... + ---
 N    N-1   N-2          1

现在，我们如何评估这笔款项？这是一个有用的事实。总和

 1     1     1           1
--- + --- + --- + ... + ---
 N    N-1   N-2          1

返回 Nth harmonic number（表示为 H_N）并且是 Θ(log N)。不仅仅是 Θ(log N)，它非常非常接近 ln N。

考虑到这一点，我们可以重写：

      1     2     3           N
     --- + --- + --- + ... + ---
      N    N-1   N-2          1

      1     1     1           1
=    --- + --- + --- + ... + ---
      N    N-1   N-2          1

            1     1           1    
+          --- + --- + ... + ---
           N-1   N-2          1

                  1           1    
+                --- + ... + ---
                 N-2          1

+                      ...


                              1    
+                            ---
                              1

这里的基本思想是将 (k + 1) / N 视为分数 1 / N 的 (k + 1) 个副本，然后像这样将它们重新组合成单独的行。

完成此操作后，请注意第一行是第 N 次谐波数 H_n，下面的项目是第 (N - 1) 次谐波数H_n-1，其下一项是(N - 2)次谐波数H_{n - 2}，等等。所以这意味着我们的小数总和等于

H₁ + H₂ + H₃ + ... + H_N

= Θ(log 1 + log 2 + log 3 + ... + log N)

= Θ(log N!) (properties of logs)

= Θ(N log N) (Stirling's approximation).

乘以这个y 前面取出的N的原始因子，我们得到整体运行时间为Θ(N² log N).

那么，这在实践中是否成立？为了找出答案，我运行对输入运行ge 的代码进行了计算，并计算了 isThere 中循环的平均迭代次数。然后，我将每个项除以 log N，并进行 polynomial-fit 回归以查看余数与 Θ(N²) 的匹配程度。回归发现最佳多项式图的多项式项为 N^2.01，这有力地支持了这一点（在乘回 log N 项后）我们正在寻找 N² log N。（请注意，运行相同的回归但没有首先划分 log N 项显示 N^2.15 的拟合，这清楚地表明了一些事情N² 除外。）

使用方程 Predicted(N) = (N² ln N) / 1.06，最后一个常数根据经验确定，我们得到上面的图，几乎绝配。

现在，快速结束这个问题。回想起来，我应该预测到运行时间几乎是 Θ(N² log N)。之所以如此，是因为这个问题与经典概率谜题 coupon collector's problem 密切相关。在那个谜题中，有 N 个不同的优惠券可供收集，并且您一直在运行dom 收集优惠券。那么问题来了——按照预期，您需要收集多少张优惠券才能获得一张优惠券？

这与我们这里遇到的问题非常吻合，在每一步中，我们都从一袋 N+1 个选项中挑选，并试图最终挑选出所有的选项。这意味着我们需要 Θ(N log N) 运行dom 在所有迭代中绘制。然而，每次抽奖的成本取决于我们所处的循环迭代，后期抽奖的成本高于早期抽奖。基于大多数平局都在后半区的假设，我应该能够猜到我们每次平局平均做 Θ(N) 工作，然后乘以得到 Θ(N² log N).但相反，我只是从头开始重新推导。哎呀

哇，那是一次旅行！希望这对您有所帮助！

带有随机对象的 while 循环的大 O 时间复杂度

Big O time complexity of a while loop with a random Object

java

random

math

big-o