一个包含 n 个字符串的列表，每个字符串的长度为 n，使用合并排序算法按字典顺序排序。这个计算的最坏情况运行时间是？
我把这个问题作为家庭作业。我知道在 O(nlogn) 时间内进行合并排序。对于长度的字典顺序，它是 n 乘以 nlogn 吗？还是 n^2 ？
最佳答案
算法的每次比较都是 O(n) [比较两个字符串是 O(n) 最坏的情况——你可能只在最后一个字符]，您在合并排序中有 O(nlogn) 比较。
因此你得到 O(nlogn * n) = O(n^2 * logn)
关于algorithm - 合并排序最坏情况下的字典排序运行时间？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9276163/