按O(n)时间对包含n个字符的字符串数组进行排序
按O(n)时间对包含n个字符的字符串数组进行排序
提问于 2020-12-01 01:19:25
问题：
我们有一个m字符串数组，它仅由小写字符组成，因此所有字符串合并后的字符总数为n。
演示如何仅使用字符比较在O(n)时间内排序字符串(按字典顺序排列)。证明你的答案是正确的。
我拥有的：
这看起来真的应该是基数排序。基排序的时间复杂度为O(k*(m+d))，其中k是包含在数组中的字符串中的最大字母数，d是“桶”的数目(假设您使用的是基排序和桶排序)，在这种情况下，我们知道我们将有26个“桶”(对于字母表中的每个字母)。因此，我们可以将时间复杂度简化为O(k*m)。
假设我是正确的，最好的方法是基数排序，我要证明的是，O(k*m) = O(n)。
我说得对吗?这是基数吗？如何证明O(k*m) = O(n)？
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-12-01 04:59:59
O(k*(m+d)) ~ O(n+kd)在你的情况下。
例如，假设您必须对"ABCD“、"ABDC”、"AB“进行排序。当您对第一个和第二个字符进行排序时，您将遍历所有三个元素。但是当您检查第三个和第四个字符时，您不必检查字符串"AB“，因为它没有第三个和第四个字母。因此，每个字母的实际遍历时间是2*3 + 2*2 = 10，这是所有字符串的长度之和(加上用于存储和检索字母的kd项)。
您只需对终止的字符串添加几个验证检查，就可以调整基数排序，结果是O(n + kd)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65083453
复制相关文章
相似问题
腾讯云开发者
