algorithm - 假设我们有一个算法接受一个字符串数组，对每个字符串进行排序，然后对整个数组进行排序。运行时间是多少？

Question

问题是:

假设我们有一个算法接受一个字符串数组，对每个字符串进行排序，然后对整个数组进行排序。运行时间是多少？

解决方法如下:

我发现上述解决方案的特殊之处在于:“您还应该考虑到您需要比较字符串。每个字符串比较需要 O(s) 时间。有 O(a log a)比较，因此这将花费 O (a*s log a) 时间。”

我们需要比较什么？

对字符串进行排序需要 s log s 时间。假设有 a 字符串，因此花费的总时间为 a*s log s

现在问题已经缩小到简单地对给定的数组进行排序，您可以在 a log a 时间内完成，因此所花费的总时间是 a*s log s + a log a = a (s log s + log a)

我的思维过程哪里出了问题？

问题取自Cracking The Coding Interview这本书

Answer 1

对数字列表进行排序假设比较发生在 O(1) 常数时间内，根据比较次数给出 nlogn 复杂度。但是，当我们对成员需要时间 x 进行比较的可枚举进行排序时，运行时间变为 xnlogn。这是因为我们正在执行一个需要 x 次，nlogn 次的 Action 。

但是，我还必须争辩说，字符串是对基数 26 的直接双射。由于我们认为以 10 为基数的比较发生在恒定时间内，因此没有理由不将其扩展到本质上是基数的数字的字符串26. 这真的取决于字符串比较机制的实现。因此，根据字符串比较的完成方式，我们最终得到两种可能的运行时。

当且仅当我们假设将字符串与以 26 为基数的数字进行比较，并且假设这可以在常数时间内完成时，您的观点是正确的。

否则，一般排序需要(比较时间)x nlogn