带有随机对象的 while 循环的大 O 时间复杂度
jos*_*urg 4 java random math big-o
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循环
简短版本：
- 预期的运行时间是?(N 2 log N)。
- 我有数学来支持这一点，以及经验数据。
这是一个图表，将完成的经验工作量与我为 N 2 log N形式的函数得到的最佳拟合近似值进行比较，该函数为 (N 2 ln N) / 1.06：
好奇的？继续阅读。:-)
让我们从这里的代码退后一步，看看实际的逻辑在做什么。代码的工作原理如下：对于数组 0, 1, 2, 3, ..., N 的每个前缀，该代码会不断地生成 0 到 N 之间的随机数，直到生成一个以前从未见过的随机数。然后它在当前阵列槽中记下该数字并移至下一个。
我们在此分析中需要一些观察结果。想象一下，我们即将进入循环的第 k 次迭代firstAlgo。关于数组的前 k 个槽的元素，我们能说什么？好吧，我们知道以下几点：
- 位置 0, 1, 2, 3, ..., k-1 处的元素都彼此不同。这样做的原因是，每次循环迭代仅在找到之前不会出现在数组中的某些内容时才会停止。
- 这些值都不等于 0，因为数组最初用 0 填充，如果 0 是在上一步中生成的，则不允许使用。
- 作为(1)和(2)的结果，槽0、1、2、...、k-1和k中的元素都是不同的。
现在，我们可以开始进行一些数学运算了。让我们看看 中循环的迭代 k firstAlgo。每次我们生成一个随机数时，我们都会查看 (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。（更正式地说，这是成功概率为 p 的几何随机变量的平均值，您可以使用期望值的正式定义和一些泰勒级数来证明这一点。）这意味着在该循环的第 k 次迭代中，期望数量在我们获得唯一的随机数之前，我们需要生成的随机数是 (N + 1) / (N - k)。
总的来说，这意味着在循环的迭代 k 上完成的预期工作量firstAlgo由 (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
返回第N 个谐波数（表示为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 1 + H 2 + H 3 + ... + H N
= ?(log 1 + log 2 + log 3 + ... + log N)
= ?(log N!)（日志的属性）
= ?(N log N) （斯特林近似）。
将其乘以我们之前提取的 N 的原始因子，我们得到整体运行时间是?(N 2 log N)。
那么，这在实践中站得住脚吗？为了找出答案，我在一系列输入上运行了代码，并计算了isThere. 然后我将每个项除以 log N 并进行多项式拟合回归，以查看余数匹配的程度？（N 2）。回归发现最佳多项式图的多项式项为 N 2.01，强烈支持（在乘回 log N 项后）我们正在查看 N 2 log N。（请注意，运行相同的回归但没有先除法log N 项显示拟合 N 2.15，这清楚地表明这里发生了除 N 2之外的其他事情。）
使用方程 Predicted(N) = (N 2 ln N) / 1.06，根据经验确定最后一个常数，我们得到上面的图，这几乎是一个完美的匹配。
现在，快速解决这个问题。回想起来，我应该几乎立即预测到运行时间将是 ?(N 2 log N)。原因是这个问题与优惠券收集者的问题密切相关，这是一个经典的概率难题。在那个谜题中，有 N 种不同的优惠券需要收集，你不断地随机收集优惠券。那么问题是 - 按照预期，您需要收集多少张优惠券才能获得每张优惠券的副本？
这与我们在这里遇到的问题非常吻合，我们在每一步都从一袋 N+1 个选项中挑选，并试图最终挑选出所有这些。这意味着我们需要在所有迭代中随机抽取 ?(N log N) 次。但是，每次绘制的成本取决于我们所处的循环迭代，后期绘制的成本高于早期绘制。基于大多数平局都在后半场的假设，我应该能够猜测我们平均每次平局会做 ?(N) 工作，然后乘以得到 ?(N 2 log N ）。但相反，我只是从头开始重新创建东西。哎呀。
呼，那是一次旅行！希望这可以帮助！