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

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

在图像中我不明白当字符串数组被排序时多余的O（s）来自何处。我得到的排序字符串数组将是O（一个日志一），我不明白为什么我们必须添加O（S）以及。

在我看来，O（一个日志a）已经关注将字符串数组中的所有字符串排序。

2016-11-19 MrBuggy

想想如何用log来比较两个长度的字符串。这是一个'O（s）'操作。有'O（a日志a）'_comparisons_，但每个比较需要'O（s）'时间。 – mrmcgreg

这张图片有一个错误 - 排序一个长度为s的字符串需要O（s）个时间，而不是O（s log s），正如文本所暗示的那样（假设一个字符串是从一个有限的字母表，并且你选择一个合适的排序算法，如quicksort，而不是像mergesort这样的保证Theta（s log s）算法。 –

它是[可争议的]（http://www.bbc.co.uk/programmes/b07zyl4b）是否排序一个字符串是O（n log n）或者只是O（n），如果字符串确实事先知道被排序，不管怎样，问题是关于“为什么添加”，而不是排序的大O一个字符串，在任何一种情况下，都需要一个“+”来表示发布的问题的最终运行成本 – mohsenmadi

在图片中，您问“为什么添加？”那么它们是独立的操作，分别对每个a字符串进行排序，每个字符串的长度是s，那就是O(a * s log s)，并且对a字符串的排列进行排序，每个字符串的长度为s，以计算每两个字符串之间的潜在比较，那是另一个O(a * s log a)。独立运营意味着“添加”。添加给出O(a * s log s + a * s log a)，这是您提取公共因素时得到的结果。

来源

2016-11-19 23:00:06 mohsenmadi

Upvoted，但你的答案包含一个小错误。 “s”表示为最长字符串的长度，而不是每个字符串的长度。当然，这并不会改变最终的结果，因为big-O是一个上限，所以假设每个字符串与最长字符串一样长。 –

谢谢。你说过，这里是一个“上限”，所以假设每个字符串的长度是最长的，这是大O计算中的常态。还有其他的（例如，欧米茄，θ）用于下界估计。 – mohsenmadi

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

回答

相关问题