在内置字符串 sort() 中使用 lambda 作为键，难以识别 Big-O

Question

我编写的以下代码获取 y 中的每个字符串并将字谜放在列表中：

>>> y = ['eat','beat','sweet','tea', 'eta', 'teews', 'leet', 'tele']
>>> y.sort(key=lambda x: sorted(x))
>>> y
['beat', 'eat', 'tea', 'eta', 'leet', 'tele', 'sweet', 'teews']

在尝试为此解决方案指定时间复杂度时，我遇到了困难。我认为它是 O(nlogn) 但我不确定 lambda 在这里实际做了什么。主要是因为我实际上不确定引擎盖下发生了什么python。

谁能阐明在 pythons 字符串排序内置函数中使用 lambda 作为键的时间复杂度？

Answer 1

排序时作为参数传递的 lambda 函数对 iterable 中的每个元素应用一次，并用于彼此之间的比较。

y.sort(key=lambda x: sorted(x)) 表示对于列表 y 中的每个元素 x，将调用 stored(x) 并将确定哪个字符串必须在最终列表中排在第一位。

由于排序确实是 O(n log n)，并且说您的列表包含 m 个平均长度 n 的字符串，我会说这里的复杂度是 O(m * (n log n) + (m log m))。

Answer 2

@Delgan 有一个很好的答案，但由于我今天在做 lambda roll，我将投入我的 0.02 美元。 lambda 只是一个匿名函数。我将你的重写为常规函数，并包含一个 print 以查看排序键的样子。

>>> def my_sorted_key_fctn(key):
...     sorted_key = sorted(key)
...     print(sorted_key)
...     return sorted_key
... 
>>> y = ['eat','beat','sweet','tea', 'eta', 'teews', 'leet', 'tele']
>>> y.sort(key=my_sorted_key_fctn)
['a', 'e', 't']
['a', 'b', 'e', 't']
['e', 'e', 's', 't', 'w']
['a', 'e', 't']
['a', 'e', 't']
['e', 'e', 's', 't', 'w']
['e', 'e', 'l', 't']
['e', 'e', 'l', 't']
>>> y
['beat', 'eat', 'tea', 'eta', 'leet', 'tele', 'sweet', 'teews']
>>>

您按键的字母按字母顺序对列表进行了排序。

但在这种情况下您不需要 lambda。如果 lambda 所做的只是调用一个与 lambda 具有相同参数的函数......那么它根本没有做任何有用的事情。就用原来的功能。

>>> y.sort(key=sorted)
>>> y
['beat', 'eat', 'tea', 'eta', 'leet', 'tele', 'sweet', 'teews']
>>>

在内置字符串 sort() 中使用 lambda 作为键，难以识别 Big-O

Using a lambda as key within builtin string sort(), hard to identify Big-O

python

big-o