问数组排序(String [])的时间复杂度是多少？

EN

说：排序是O(n logn)的问题是，这是一个不完整的、因此不明确的、未定义的语句。目前还不清楚这意味着什么。问题是:您没有定义n是什么。

现在，在实践中，n通常在上下文中是显而易见的。例如，如果我说：“对整数数组进行排序是O(n logn)，假设是最优排序算法”，那么几乎所有听到这一结果的人都会立即意识到，虽然我没有明确指出n是什么，但很明显，我的意思是:n=该数组中的in数。

让我们回到你的问题:现在n不再清楚了。

N是数组中字符串的#吗？N是该数组中所有字符串的平均字符#吗？

我们讨论的是两个独立的变量。因此，要正确地描述这个问题的大O表示法的性能特征，您可以这样说：

例如：str = {"Hello", "World", "John", "Doe"}

• Let n是str数组中的元素数，

• 是str数组中字符串的平均#H 217H 118，然后在该数组上调用Arrays.sort(str)将具有O(m * n log n).

的性能特征。

之所以是O(m*n logn)，是因为排序算法本身将运行O(n logn)比较操作来执行排序。每个比较操作都需要O(m)时间来完成，尽管这是最坏的情况:给定，比方说，Hello和World，即使对于这两个操作，比较只在一个步骤之后就完成了；算法对H和W进行比较，并立即回答，甚至从来不看ello或orld。但是如果字符串是Hello1、Hello2、Hello3和Hello4，那么每次比较两个字符串时，这都是一个保证的5‘步骤’，并且会有O(n logn)比较。