Pythonsort()时间复杂度如何随非O(1)复杂度的lambda函数变化?

我有一个数组“日志”,其中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]))多少?

回答

根据文档(强调我的):

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

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


以上是Pythonsort()时间复杂度如何随非O(1)复杂度的lambda函数变化?的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>