algorithm - 如何在字符串数组中对字符串进行排序，然后对该数组进行排序，结果是 O(a*s(loga+logs))？

Question

在图像中，我不明白在对字符串数组进行排序时额外的 O(s) 从何而来。我知道对字符串数组进行排序将是 O(a log a)，我不明白为什么我们还必须添加 O(s)。

在我看来，O(a log a) 负责对字符串数组中的所有字符串进行排序。

Answer 1

卡在同一个例子上了!请记住，对 n 个字符的数组进行排序需要花费 nlogn 时间。对于最后的排序，如果我们假设数组中的每个字符串的长度为 1，那么我们再次只是对 a 字符进行排序，所以我们得到 aloga 项，但是最差的每个字符串的 case 长度是 s 所以你需要做 aloga 比较 s 次。