如何对字符串数组中的字符串进行排序，然后对数组进行排序，得出O（a * s（loga + logs））？

Question

在图像中，当对字符串数组进行排序时，我不明白多余的O从何而来。我得到排序的字符串数组将是O（log a），我不明白为什么我们也必须添加O（s）。

在我看来，O（a log a）负责整理字符串数组中的所有字符串。

Answer 1

卡在同一个例子上！请记住，nlogn对 n 个字符的数组进行排序需要花费时间。对于最后的排序，如果我们假设数组中的每个字符串的长度为 1，那么我们再次只是对a字符进行排序，因此我们得到了aloga术语，但是每个字符串的最坏情况长度是s这样，您需要进行aloga比较s次数。

Answer 2

在图片中你问“为什么要添加？” 嗯，它们是独立的操作，一种对每个a字符串进行排序，每个字符串的长度为s，即O(a * s log s)，一种对a字符串数组进行排序，每个的长度是s计算每两个字符串之间的潜在比较，这是另一个O(a * s log a)。独立操作意味着“添加”。添加 give O(a * s log s + a * s log a)，这是您提取公因数时得到的。