Update 09.Array-Bucket-Sort.md

itcharge · itcharge · commit 9c0b7bec7d25 · 2022-01-17T13:46:33.000+08:00
diff --git a/Contents/01.Array/02.Array-Sort/09.Array-Bucket-Sort.md b/Contents/01.Array/02.Array-Sort/09.Array-Bucket-Sort.md
@@ -27,8 +27,8 @@
 
 ## 4. 桶排序算法分析
 
-- 桶排序可以在线性时间内完成排序，当输入元素个数为 `n`，桶的个数是 `m` 时，桶排序时间复杂度为 $O(n + m)$。
-- 由于桶排序使用了辅助空间，所以桶排序的空间复杂度是 `o(n + m)`。
+- 桶排序可以在线性时间内完成排序，当输入元素个数为 `n`，桶的个数是 `m` 时，每个桶里的数据就是 `k = n / m` 个。每个桶内排序的时间复杂度为 $O(k * log_2k)$。`m` 个桶就是 $m * O(k * log_2k) = m * O((n/m)*log_2(n/m)) = O(n*log_2(n/m))$。当桶的个数 `m` 接近于数据个数 `n` 时，$log_2(n/m)$ 就是一个较小的常数，所以排序桶排序时间复杂度接近于 $O(n)$。
+- 由于桶排序使用了辅助空间，所以桶排序的空间复杂度是 $o(n + m)$。
 - 如果桶内使用插入排序算法等稳定排序算法，则桶排序也是 **稳定排序算法**。
 
 ## 5. 桶排序代码实现
