LeetCode 988两种解法时间复杂度与实际运行耗时疑问

我给LeetCode第988题写了两种解法：

• 解法一：先DFS遍历生成所有从根到叶子的路径字符串（反转后存起来），最后排序取字典序最小的。
• 解法二：DFS遍历过程中实时维护当前最小的字符串，每到叶子节点就和当前最小值比较更新。

按理论复杂度分析，解法一是O(n logn)（n为叶子节点数），解法二是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):
            nonlocal shortest
            if not node.left and not node.right:
                current = (string + d[node.val])[::-1]
                if not shortest:
                    shortest = current
                else:
                    shortest = min(shortest, current)
            if node.left:
                dfs(node.left, string + d[node.val])
            if node.right:    
                dfs(node.right, string + d[node.val])

        dfs(root, '')
        return shortest

为啥解法二反而更慢？ #

主要有这几个核心原因：

1. 内置排序的效率碾压：Python的sorted()用的是Timsort算法，完全由C实现，执行速度极快。而解法二中每次比较字符串的min()操作是在Python解释器层面执行的，哪怕理论复杂度更低，实际执行的开销反而更高——尤其是当叶子节点数量不算特别多的时候，Timsort的C级执行速度能轻松追上甚至超过Python层面逐次比较的开销。
2. 字符串比较的重复开销：解法二每到一个叶子节点就要和当前最小值做一次完整的字符串比较，如果树的深度大、叶子多，很多前缀相同的字符串会被反复比较；而Timsort在排序时会利用字符串的前缀共性做优化，减少重复比较的次数。
3. nonlocal的额外开销：解法二中用nonlocal访问外部变量shortest，每次访问和修改都要经过Python的变量作用域查找，比解法一中直接往列表append（这是一个 amortized O(1) 的操作，且列表操作的底层也是C实现）多了一层开销。
4. 测试用例的波动：LeetCode的运行时间本身存在一定波动，5ms的差距可能属于正常误差范围，但如果多次测试都是解法二慢，那上面的原因就是核心因素。

内容的提问来源于stack exchange，提问作者Hayden