带有随机对象的while循环的java大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中的main for循环也是如此

Answer 1

你可以凭经验来做。只需运行代码并计时，使用不同的值N。我这样做了，复杂性似乎是O（N^2）。我做了一系列的测试，每一次都是N的翻倍，而时间似乎从未从大约翻两番的水平上后退过。我厌倦了在N=256000时等待，这大约需要20万毫秒

如果你想走这条路，你会想做更多的运行更仔细的分析。你可以设置一个外部循环来持续进行批量测试，比如说每级10次，对它们进行计时，然后将N加倍，然后再次进行测试。。。记录所有的时间。你可以在一夜之间运行测试，并从经验上对行为有一个相当清晰的认识

如果这不是你想要的方式，至少可以是一种反复检查你答案的方式

Answer 2

简短版本：

• 预期运行时间为Θ（N²logn）
• 我有数学和实证数据来支持这一点

这是一个曲线图，将所做的经验工作量与我得到的形式为N²logn的函数的最佳拟合近似值进行比较，其为（N²ln）/1.06：

好奇？继续读下去。：-）

让我们从这里的代码中退一步，看看实际的逻辑在做什么。代码的工作原理如下：对于数组的每个前缀0、1、2、3。。。，N、 该代码连续生成0到N之间的随机数，直到生成一个以前从未见过的随机数。然后，它将该数字写在当前阵列插槽中，并转到下一个插槽

我们在分析中需要的一些观察结果。假设我们即将进入firstAlgo中循环的第k次迭代。关于阵列的前k个插槽的元素，我们可以说些什么？那么我们知道以下几点:

1. 位置0、1、2、3…处的元素。。。，k-1各不相同。这样做的原因是，每次循环迭代只有在找到某个在该点之前不会出现在数组中的内容时才会停止
2. 这些值都不等于0，因为数组最初是用0填充的，如果在上一步中生成了0，则不允许使用0
3. 根据（1）和（2），插槽0、1、2……中的元件。。。，k-1和k都是不同的

现在，我们可以开始数学了。让我们看看firstAlgo中循环的迭代k。每次生成一个随机数时，我们都会查看（k+1）数组插槽，以确保该数字不会出现在那里。（顺便说一句，我将使用这个数量作为所做总功的代理，因为大部分能量将用于扫描该阵列。）所以，我们需要问一下，在我们找到一个唯一的数字之前，我们将产生多少个数字

以上列表中的事实（3）在这里很有用。它说在迭代k中，数组中的第一个k+1插槽彼此不同，我们需要生成一个不同于所有这些插槽的数字。我们可以选择N+1个随机数选项，因此我们可以选择（N+1）-（k+1）=N-k个选项来选择那些不曾使用过的随机数。这意味着我们选择一个尚未出现的数字的概率是（N-k）/（N+1）

快速检查以确保这个公式是正确的：当k=0时，我们可以生成除0以外的任意随机数。有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次迭代中，在得到唯一的随机数之前，我们需要生成的预期随机数是（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）和isΘ（logn）。不仅仅是Θ（logn），它非常非常接近ln

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

      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).

将其乘以我们之前提取的原始因子N，我们得到的总体运行时间是Θ（N²logn）

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

使用预测的方程（N）=（N²ln）/1.06，用经验确定的最后一个常数，我们得到上面的图，这几乎是一个完美的匹配

---

现在，快速结束这个问题。回想起来，我本应该预测运行时几乎是立即发生的（N²logn）。原因是这个问题与coupon collector's problem密切相关，这是一个经典的概率难题。在这个谜题中，有N个不同的优惠券要收集，你一直随机收集优惠券。问题是，在期望中，你需要收集多少张优惠券，然后才能获得一份

这与我们在这里遇到的问题非常吻合，在每一步中，我们都从一袋N+1选项中选择，并试图最终选择所有选项。这意味着我们需要在所有迭代中进行Θ（logn）随机绘制。然而，每次绘制的成本取决于我们所处的循环迭代，后期绘制的成本高于早期绘制的成本。基于大多数绘图都在后半部分的假设，我应该能够猜到，我们平均每绘图做Θ（N）个工作，然后乘以该值得到Θ（N²logn）。但是，我只是从零开始重新驱动。哎呀

唷，那真是一次旅行！希望这有帮助

Answer 3

记住，Big-O是最坏的行为。正如其中一条评论中提到的，这有可能永远不会终止，从而导致无限大的O，因为这段代码是不确定的

对于一个平均情况，random做了预期的事情。您正在查看isThere函数的O（N）。对于最后一次查找值的迭代，您将平均N次操作。在这一点上，你达到了O（N^2）。最后，您需要重复此操作N次以填充数组，这将导致O（N^3）