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

Question

我有一个数组'logs'，其中 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

根据documentation (强调我的):

Both list.sort() and sorted() have a key parameter to specify a function to be called on each list element prior to making comparisons.

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