在 O(n) 时间内对包含 n 个字符的字符串数组进行排序
Sorting array of strings containing n characters in O(n) time
问题：
我们有一个仅由小写字母组成的 m 字符串数组
字符使得所有字符串中的字符总数
合并为 n.
显示如何仅使用字符比较在 O(n) 时间内对字符串进行排序（按字典顺序）。证明你的答案。
我有：
这看起来确实应该是基数排序。基数排序的时间复杂度为 O(k*(m+d))，其中 k 是数组中包含的字符串中字母的最大数量，d 是“桶”的数量（假设您使用基数排序桶排序）在这种情况下我们知道我们将有 26 个“桶”（对于字母表中的每个字母）。因此我们可以将时间复杂度简化为O(k*m).
假设我是正确的，最好的方法是基数排序，我正在努力证明的是 O(k*m) = O(n)。
我说这是基数排序对吗？
我如何证明 O(k*m) = O(n)？
O(k*(m+d)) ~ O(n+kd) 在你的情况下。
例如，假设您必须对 ["ABCD"、"ABDC"、"AB"] 进行排序。当您对第一个和第二个字符进行排序时，您会遍历所有 3 个元素。但是当您检查第三个和第四个字符时，您不必检查字符串“AB”，因为它没有第三个和第四个字母。因此，您实际遍历每个字母的时间将是 2*3 + 2*2 = 10，这是所有字符串长度的总和（加上用于存储和检索字母的 kd 项）。
您只需要通过在终止字符串上添加一些验证检查来调整基数排序，它会达到 O(n + kd)
问题：
我们有一个仅由小写字母组成的 m 字符串数组 字符使得所有字符串中的字符总数 合并为 n.
显示如何仅使用字符比较在 O(n) 时间内对字符串进行排序（按字典顺序）。证明你的答案。
我有：
这看起来确实应该是基数排序。基数排序的时间复杂度为 O(k*(m+d))，其中 k 是数组中包含的字符串中字母的最大数量，d 是“桶”的数量（假设您使用基数排序桶排序）在这种情况下我们知道我们将有 26 个“桶”（对于字母表中的每个字母）。因此我们可以将时间复杂度简化为O(k*m).
假设我是正确的，最好的方法是基数排序，我正在努力证明的是 O(k*m) = O(n)。
我说这是基数排序对吗？ 我如何证明 O(k*m) = O(n)？
O(k*(m+d)) ~ O(n+kd) 在你的情况下。
例如，假设您必须对 ["ABCD"、"ABDC"、"AB"] 进行排序。当您对第一个和第二个字符进行排序时，您会遍历所有 3 个元素。但是当您检查第三个和第四个字符时，您不必检查字符串“AB”，因为它没有第三个和第四个字母。因此，您实际遍历每个字母的时间将是 2*3 + 2*2 = 10，这是所有字符串长度的总和（加上用于存储和检索字母的 kd 项）。
您只需要通过在终止字符串上添加一些验证检查来调整基数排序，它会达到 O(n + kd)