字符串数组中查找最小/最大元素的时间复杂度分析

调用min(arr)或max(arr)的时间复杂度并不是O(n²)，而是O(N*K)，其中：

• N是数组的元素个数
• K是数组中字符串的最大长度

具体分析： #

• 和数值数组的逻辑类似，min/max函数需要遍历数组中的N个元素，进行N-1次比较操作。
• 每次比较两个字符串时，最坏情况下需要遍历到字符串的末尾才能分出大小（比如两个字符串前K-1个字符完全相同，或其中一个是另一个的前缀），这一步的时间复杂度是O(K)。
• 把所有比较的成本加起来，总时间复杂度就是O(N*K)。

以你给出的例子arr=["abcd","abdd","abba", "abca"]为例：
数组长度N=4，字符串最大长度K=4，总共需要3次字符串比较，每次最多4次字符对比，总操作数是34=12，完全符合O(NK)的计算逻辑。

为什么不是O(n²)？ #

O(n²)的复杂度意味着操作数和数组长度的平方成正比，但这里的K是字符串的最大长度，和数组元素个数N是独立的变量。只有当K和N成正比（比如数组第i个字符串的长度等于i）时，才会出现O(N²)的特殊情况，但这不属于常规场景。

内容的提问来源于stack exchange，提问作者Anirudh Kakati