哪个运行时间应该更快？

Question

我针对 Leetcode 问题 988 实现了两种解决方案：一种创建字符串列表并对其进行排序以返回最小的（按字典顺序），另一种仅在整个生成过程中跟踪最小的。

我分析两者的运行时间分别是 O(nlogn) 和 O(n)，那为什么 LeetCode 告诉我第二种实现总体慢了 5ms？

拳头解决方案：

class Solution:
    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
        d = dict(enumerate(string.ascii_lowercase))
        words = []

        def dfs(node, string):
            if not node.left and not node.right:
                words.append((string + d[node.val])[::-1])
            if node.left:
                dfs(node.left, string + d[node.val])
            if node.right:    
                dfs(node.right, string + d[node.val])

        dfs(root, '')
        return sorted(words)[0]

第二种解决方案：

class Solution:
def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
    d = dict(enumerate(string.ascii_lowercase))
    shortest = None

    def dfs(node, string):
        if not node.left and not node.right:
            nonlocal shortest
            if not shortest:
                shortest = (string + d[node.val])[::-1]
            else:
                shortest = min(shortest, (string + d[node.val])[::-1])
        if node.left:
            dfs(node.left, string + d[node.val])
        if node.right:    
            dfs(node.right, string + d[node.val])

    dfs(root, '')
    return shortest

Answer 1

Python 级别的临时调用相对昂贵。在第二个解决方案中，您为树中的每个节点调用

min()

一次。在第一个解决方案中，您根本不调用

min()

- 只是在最后调用

sort()

一次。

sort()

的内部实现可以以比 Python 级代码高得多的速度进行比较。

如需更多信息，请将

return sorted(words)[0]

替换为

return min(words)

- 根本不需要排序。而且这可能仍然会慢一些！不知道 - 尝试一下。隐藏的混杂因素是

sort()

预先分析列表，看看它是否可以找到更快的、特定于类型的方式来启动比较（对于类型

str

，它可以）。

min()

不会这样做 - 在每次比较时它都会从头开始查看比较数的类型并推断需要调用哪个特定比较函数。这需要时间，一遍又一遍。

总而言之，适用于这两种解决方案的代码中最糟糕的“理论”方面是重复执行

[::-1]

。反转字符串所需的时间与其长度成正比，对于深度为

O(d**2)

的树来说，这总体上会产生

d

费用。但逆转很快，所以这可能并不重要，除非树长得很深。

另一种方法是使用非本地

collections.deque()

字符，并在向下的方向上通过

.appendleft()

添加字符，并在向上的方向上通过

.popleft()

删除字符。这些是

O(1)

操作，不需要反转，并且内存中只有一个正在进行的双端队列。因为双端队列也是序列，所以它们也支持字典比较。当您找到新的最小值时，请使用

deque_object.copy()

将副本绑定到非本地“总体获胜者”变量名称。