问题是:
假设我们有一个算法接受一个字符串数组，对每个字符串进行排序，然后对整个数组进行排序。运行时间是多少？
解决方法如下:
我发现上述解决方案的特殊之处在于:“您还应该考虑到您需要比较字符串。每个字符串比较需要 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这本书
最佳答案
对数字列表进行排序假设比较发生在 O(1) 常数时间内，根据比较次数给出 nlogn 复杂度。但是，当我们对成员需要时间 x 进行比较的可枚举进行排序时，运行时间变为 xnlogn。这是因为我们正在执行一个需要 x 次，nlogn 次的 Action 。
但是，我还必须争辩说，字符串是对基数 26 的直接双射。由于我们认为以 10 为基数的比较发生在恒定时间内，因此没有理由不将其扩展到本质上是基数的数字的字符串26. 这真的取决于字符串比较机制的实现。因此，根据字符串比较的完成方式，我们最终得到两种可能的运行时。
当且仅当我们假设将字符串与以 26 为基数的数字进行比较，并且假设这可以在常数时间内完成时，您的观点是正确的。
否则，一般排序需要(比较时间)x nlogn
关于algorithm - 假设我们有一个算法接受一个字符串数组，对每个字符串进行排序，然后对整个数组进行排序。运行时间是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56322033/