8000 feat(algo): add · shgopher/408@d6c3428 · GitHub
[go: up one dir, main page]
Skip to content

Commit d6c3428

Browse files
shgophershgopher
committed
feat(algo): add
1 parent 47a53e1 commit d6c3428

File tree

2 files changed

+124
-4
lines changed

2 files changed

+124
-4
lines changed

‎算法/算法/洗牌算法/README.md

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
<!--
2+
* @Author: shgopher shgopher@gmail.com
3+
* @Date: 2022-02-22 03:15:15
4+
* @LastEditors: shgopher shgopher@gmail.com
5+
* @LastEditTime: 2024-04-02 15:13:15
6+
* @FilePath: /408/算法/算法/洗牌算法/README.md
7+
* @Description:
8+
*
9+
* Copyright (c) 2024 by shgopher, All Rights Reserved.
10+
-->
11+
# 洗牌算法
12+
洗牌算法是指将一组有序的元素重新进行排列顺序的算法，通常用于生成随机排列。洗牌算法常见的应用包括：
13+
14+
1. **生成游戏规则**：在很多棋牌游戏中，需要随机打乱卡牌或棋子的顺序，以确保游戏的公平性。
15+
16+
2. **加密和安全**：在密码学中，洗牌算法可用于加密密钥的生成，以增加密码的强度。
17+
18+
3. **随机抽样**：在统计学和模拟领域，常常需要从一个总体中随机选取样本进行研究和分析。
19+
20+
常见的洗牌算法有：
21+
22+
1. **Fisher-Yates 洗牌算法**：也被称为 Knuth 洗牌算法，是一种非常高效和简单的现代洗牌算法。它通过遍历数组，并在每一步中随机交换当前元素与剩余未处理的元素中的一个。时间复杂度为 O(n)。
23+
```go
24+
import (
25+
"math/rand"
26+
"time"
27+
)
28+
29+
func init() {
30+
rand.Seed(time.Now().UnixNano())
31+
}
32+
33+
func shuffle(arr []int) []int {
34+
for i := len(arr) - 1; i > 0; i-- {
35+
j := rand.Intn(i + 1) //[0,i]
36+
arr[i], arr[j] = arr[j], arr[i]
37+
}
38+
return arr
39+
}
40+
```
41+
2. **Sattolo's 算法**：也是一个线性时间算法，与 Fisher-Yates 类似，但更加简洁。
42+
43+
3. **冒泡排序洗牌算法**：利用冒泡排序的交换操作特性，通过大量的交换操作来达到随机化的目的。时间复杂度为 O(n^2)。
44+
45+
4. **插入排序洗牌算法**：类似于冒泡排序洗牌，利用插入排序的过程来达到随机洗牌的效果。
46+
47+
## 如何保证真随机性
48+
49+
假设我们有一个真正的随机数生成器，能够产生真正的随机数序列，那么 Fisher-Yates 洗牌算法确实可以保证生成真正随机的排列。其原因如下：
50+
51+
1. **等概率性**
52+
53+
Fisher-Yates 算法在每一步中，都会从剩余的未处理元素中等概率随机选择一个元素与当前元素交换位置。由于使用的是真正的随机数生成器，因此每个元素被选中的概率都是相等的 1/(n-i)。这保证了算法得到的最终排列是等概率的。
54+
55+
2. **无后效性**
56+
57+
Fisher-Yates 算法在处理每个元素时，只依赖于当前步骤随机选择的结果，而与之前步骤的结果无关。也就是说，算法在每一步都是独立无后效的。这个性质保证了算法在任何中间状态下，都可以将剩余元素等概率地排列。
58+
59+
3. **排列的可达性**
60+
61+
Fisher-Yates 算法可以生成全排列 n！中的任何一种排列，并且每一种排列的概率都是相等的 1/n！。这是因为算法将第一个元素与剩余元素中随机选择的一个交换位置，对于剩余的 n-1 个元素，又以同样的方式独立地进行随机交换，依次类推。因此，任意一种排列的生成路径都是等概率的。
62+
63+
4. **不可预测性**
64+
65+
由于使用了真正的随机数生成器，每一步中随机选择的结果都是真正随机且不可预测的。这意味着生成的排列序列不可能事先预测或重现，除非知道了完整的随机数序列。
66+
67+
从概率论的角度来看，Fisher-Yates 算法利用了真随机数生成器产生的独立同分布随机变量，将它们独立地应用于排列生成的每一个步骤。由于每一步的操作都是独立等概率的，因此最终生成的排列也就是等概率的。同时，由于每一步都利用了真正的随机性，因此整个算法也具有了真正的随机性。
68+
69+
当然，这种分析是建立在我们拥有真正的随机数生成器的前提之上。在实际计算机系统中，由于使用的都是伪随机数生成器，所以 Fisher-Yates 算法产生的排列只能被认为是 “近似随机” 的，其随机性质取决于伪随机数生成器的质量。
70+
71+
### 等概率性的数学论证
72+
73+
在 Fisher-Yates 算法中，每一步选择要交换的元素时，确实是从剩余未处理的元素中随机选取。因此，被选中的概率会随着剩余元素个数的减少而变化。
74+
75+
具体来说，对于第一个元素，它被选中的概率是 1/n。对于第二个元素，它被选中的概率是 1/(n-1)。以此类推，对于第 i 个元素，它被选中的概率是 1/(n-i+1)。
76+
77+
这看起来似乎破坏了等概率性的假设。然而，我们需要注意到，虽然每个元素被选中的概率不同，但每个排列出现的概率却是相同的。
78+
79+
我们可以这样计算：对于任意一个长度为 n 的排列，它出现的概率是：
80+
81+
(1/n) *(1/(n-1)) * (1/(n-2)) *...* (1/1) = 1/n！
82+
83+
也就是说，虽然每个元素被选中的概率不同，但是通过这些不同的概率相乘，最终每一种可能的排列出现的概率都是相同的 1/n！。
84+
85+
这个性质即保证了 Fisher-Yates 算法生成的排列是均匀分布的，任何一个排列出现的概率都是相等的。
86+
87+
算法在每个中间步骤中，被选中元素的概率分布是不均匀的。但是，最终的排列分布仍然是均匀的，这正是 Fisher-Yates 算法的精妙之处。
88+
89+
通过这种 “不均匀选择” 与 “均匀输出” 的性质，Fisher-Yates 算法在线性时间复杂度下，就能够生成真正均匀随机的排列。这种看似矛盾的性质，实际上是算法的核心原理所在。

‎算法/算法/蓄水池算法/README.md

Lines changed: 35 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22
* @Author: shgopher shgopher@gmail.com
33
* @Date: 2024-04-02 14:35:26
44
* @LastEditors: shgopher shgopher@gmail.com
5-
* @LastEditTime: 2024-04-02 14:53:07
5+
* @LastEditTime: 2024-04-02 15:29:31
66
* @FilePath: /408/算法/算法/蓄水池算法/README.md
77
* @Description:
88
*
@@ -43,7 +43,7 @@
4343

4444
通过这种 “无偏” 的随机替换过程，蓄水池算法能够保证从 `n` 个数据项中选取 k 个样本，每个数据项被选中的概率都是相等的 `k/n`。这一性质使得它成为一个公平且高效的随机采样算法。
4545
## 代码实现
46-
### GO语言版
46+
### GO 语言版
4747
普通版，在普通版中我们默认数据的来源是固定个数的数据，所以这里我们直接使用数组作为数据来源。
4848
```go
4949
import (
@@ -69,7 +69,7 @@ func ReservoirSample(stream []int, k int) []int {
6969
return reservoir
7070
}
7171
```
72-
但是现实中我们很容易遇到流的情况，也就是说数据其实不来源于数组而是一个channel，那么让我们实现一下 channel的情况
72+
但是现实中我们很容易遇到流的情况，也就是说数据其实不来源于数组而是一个 channel，那么让我们实现一下 channel 的情况
7373

7474
```go
7575
import (
@@ -131,4 +131,35 @@ function reservoirSample<T>(stream: Iterable<T>, k: number): T[] {
131131

132132
return reservoir;
133133
}
134-
```
134+
```
135+
## 蓄水池算法和洗牌算法的异同点
136+
137+
蓄水池抽样算法 (Reservoir Sampling) 和洗牌算法 (Shuffling Algorithm) 虽然都用于从一个集合中随机选取元素，但它们的适用场景和实现方式有所不同。下面是它们的异同点比较：
138+
139+
**异同点：**
140+
141+
1. **适用场景**：
142+
- 蓄水池抽样算法适用于从一个未知大小的数据流中随机选取 k 个元素，并且只需要线性空间。
143+
- 洗牌算法则适用于从一个已知大小的数组或列表中随机选取任意个数的元素，包括全排列。
144+
145+
2. **实现方式**：
146+
- 蓄水池抽样算法通过在每个元素到来时，以一定的概率将其保留到蓄水池 (reservoir) 中，从而在线性时间内获得随机样本。
147+
- 洗牌算法则通过交换元素的位置来打乱原有顺序，从而生成一个随机的排列。
148+
149+
3. **时间复杂度**：
150+
- 蓄水池抽样算法的时间复杂度为 O(n)，其中 n 为数据流的大小。
151+
- 洗牌算法的时间复杂度通常为 O(n)，其中 n 为数组或列表的长度。
152+
153+
4. **空间复杂度**：
154+
- 蓄水池抽样算法仅需要常数空间来存储样本，空间复杂度为 O(k)，其中 k 为需要抽取的样本大小。
155+
- 洗牌算法它通常是在原数据上进行就地操作。所以空间复杂度是 O(1)。
156+
157+
**相同点：**
158+
159+
1. 它们都可以用于从一个集合中随机选取元素，并且可以保证选取结果的等概率性。
160+
161+
2. 它们都利用了随机数来实现随机选取，并且通过概率分析可以证明其正确性。
162+
163+
3. 它们都具有线性时间复杂度，适合处理大规模数据。
164+
165+
总的来说，蓄水池抽样算法更适合于从大型数据流中在线获取随机样本，而洗牌算法则更适合于对已知大小的数组或列表进行随机排列。两种算法在不同的场景下都有其适用之处，并且都是实现等概率随机抽样的经典算法。

0 commit comments

Comments
 (0)
0