Python sort() 时间复杂度如何随非 O(1) 复杂度的 lambda 函数变化？

Question

我有一个数组“日志”，其中logs = ["1 art can", "2 own kit dig", "3 art zero", "4 art can"]. 每个元素都是一个字符串，它有一个序列号，后面跟着一堆单词。我需要按字符串内容的字典顺序对数组进行排序（不包括序列号）。如果数组中的两个字符串内容相同，我需要根据它们的序列号对它们进行排序。

我将 sort() 函数与 lambda 函数结合使用，后者又使用 split() 函数。用法如下： logs.sort(key=lambda x: (x.split()[1:], x.split()[0]))

我知道 sort() 的时间复杂度是 O(nlog(n)) 而 split() 本身的时间复杂度是 O(n)。假设有 n 个字符串，每个字符串的长度为 m，那么 的有效时间复杂度是logs.sort(key=lambda x: (x.split()[1:], x.split()[0]))多少？

Answer 1

根据文档（强调我的）：

list.sort() 和 sorted() 都有一个 key 参数来指定在进行比较之前要在每个列表元素上调用的函数。

所以所有的键都计算一次，而不是在进行所有比较时。执行所有关键计算的复杂性被添加到排序的复杂性中。因此，整体复杂性将是具有较大顺序的那个。