分析如下随机排序算法的时间复杂性。 输入：n 个不同的值 x1,x2,…,xn 输出：x1,x2,…,xn排序后的结果 步骤：1. 从 x1,x2,…,xn 均匀随机抽取 y1 2. For k=2 To n 3. 从{x1,…,xn}\\{y1,y2,…,yk-1}中均匀随机抽取 yk; 4. If yk<yk-1 Then goto 1; 5. 输出 y1,y2,…,yn

这个算法的时间复杂性是O(n^2)。因为对于每一个k，从剩下的{x1,...,xn}\{y1,y2,...,yk-1}中去随机抽取yk，需要进行k-1次比较才能判断yk的值是否小于yk-1的值。所以k的取值范围是2到n，那么总的计算次数就是1+2+...+(n-1) = n*(n-1)/2，也就是O(n^2)。

相关问题

分析如下随机排序算法的时间复杂性。 输入：n 个不同的值 x1,x2,…,xn 输出：x1,x2,…,xn排序后的结果 步骤：1. 从 x1,x2,…,xn 均匀随机抽取 y1 2. For k=2 To n 3. 从{x1,…,xn}\{y1,y2,…,yk-1}中均匀随机抽取 yk; 4. If yk<yk-1 Then goto 1; 5. 输出 y1,y2,…,yn

这个随机排序算法的时间复杂度是 O(n^2)，其中 n 是要排序的元素个数。因为该算法会做 n 次外层循环，每次循环需要做 k-1 次内层循环，而每次内层循环的概率为 (k-1)/k，因此平均来说需要做 (k-1)/k 次比较，总共需要做的比较次数约为 ∑(k=2 to n) (k-1)/k * n，这个数量级是 O(n^2)。实际上，该算法的运行时间还会受到元素比较和交换的代价的影响，因此理论上的时间复杂度只是一种上限估计。