延绪的水上书
0%

随机算法

发表于 更新于 分类于 Disqus：

随机算法

对于一个算法，它的平均执行速度很快，但很可能存在一些特定的输入，使得算法效率很低。如果这样的输入经常出现，那么算法的实际执行效率就会低于期望的效率。为了避免这样的情况，我们常常采用随机算法。

不失一般性地，假设给定一个数组 A，包含元素 1~n，我们讨论如何构造 A 的随机排列。

注意：我们让随机发生在算法上，而不是在输入分布上。

Permute-By-Sorting

一个通常的方法是：

  • 为数组的每个元素 A[i] 赋一个随机的优先级 P[i]，
  • 然后依据优先级对数组 A 中的元素进行排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import random

def sort_array_by_priority(A):
    n = len(A)
    
    # 为数组的每个元素分配随机优先级
    # 元组列表，包含元素和随机优先级
    P = [(v, random.random()) for v in A]
    
    # 根据优先级对数组元素进行排序
    # 根据元组的第二个元素（优先级）排序
    P.sort(key=lambda x: x[1])
    
    # 根据排序后的优先级更新原数组 A
    # 只取排序后的元素值
    A = [v for v, p in P]
    
    return A

# 示例
A = [1, 3, 5, 7, 9]
sorted_A = sort_array_by_priority(A)
print(sorted_A)

这种随机算法的时间复杂度取决于排序算法的选择。如果采用的是归并、快排，那么时间复杂度可以达到 **O(n·lgn)**。

Randomize in Place

产生随机排列的更好方法是：原址排列给定数组。

过程如下：

  • 在进行第 i 次迭代时，元素 A[i] 是从元素A[i] 到 A[n] 中随机选取的。
  • 且第 i 次迭代以后， A[i]不再改变。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import random

def randomize_in_place(A):
    n = len(A)
    for i in range(n):
        # 生成从 i 到 n-1 的随机整数
        j = random.randint(i, n-1)
        
        # 交换 A[i] 与 A[j]
        A[i], A[j] = A[j], A[i]

# 示例
A = [1, 2, 3, 4, 5]
randomize_in_place(A)
print(A)