准确的大O分析
假设您需要生成第一个N个整数的随机排列。例如，{4、3、1、5、2 }和{3、1、4、2、5}是合法排列，但{5、4、1、2、1}不是，因为一个数字(1)重复，另一个(3)丢失。这个例程经常用于算法的仿真。我们假设存在一个随机数发生器RandInt(i，j)，它以相同的概率在i和j之间产生。以下是三种算法：
(i)从A到a-1填充数组A，如下所示:若要填充Ai，请生成随机数，直到得到A、A1、…中尚未包含的数组。，Ai-1.
(ii)与演算法(i)相同，但保留一个称为使用阵列的额外阵列。当随机数Ran第一次放入数组A中时，设置UsedRan = true。这意味着当使用随机数填充Ai时，可以一步进行测试，以确定是否使用了随机数，而不是第一个算法中的(可能)i步骤。
(iii)填充数组，使Ai = i+1。
for (i=1; i<n; i++)
swap (A[i], A[RandInt(0,i)]);尽可能准确地(大O)分析每种算法的预期运行时间。
有人能帮忙吗？因为我只是学了这一章，不太明白这个问题想要什么..
回答 2
Stack Overflow用户
发布于 2014-04-03 04:57:43
I:你必须填满N个插槽，但是当你不断地填充时，你不太可能得到一个有效的数字。如果您已经填充了M个槽，那么获得一个有效数字的机会是1-(M/N)。此外，随着列表变得更长，您需要对整个过程进行迭代。N个数字* O(N)猜测每一个时隙* O(N)检查数是否已经包含= O(N^3) (O(N) )检查每个数字，因为最坏的情况是最后一个数，1/N得到未使用的数的机会)
现在我们不需要对每个检查迭代整个数组，所以只有O(N^2)
交换需要恒定的时间，我们遍历整个数组一次，所以O(N)
我想我把这些都做对了，但我很容易就错过了一些东西。希望这能有所帮助。
Stack Overflow用户
发布于 2014-04-03 04:55:18
选项4:用从1到n的值填充List / Collection，然后对集合进行洗牌。O(n) + ~O(n) => O(n)
https://stackoverflow.com/questions/22828094
复制相似问题
腾讯云开发者
