自定义字典与Python原生字典的Big O复杂度分析异常问题

我实现了两个自定义字典，一个基于双向链表，另一个基于二叉搜索树，二者都具备基础的增查功能。我想估算它们的大O复杂度，并和Python原生字典对比，但测试结果和预期不符：

• 预期复杂度：Python原生字典O(1)，链表实现O(n)，二叉搜索树实现O(log n)
• 实际问题：绘图趋势看似合理，但时间数据列表里的数值呈现随机增长的情况

自定义字典实现代码 #

class dict_linear:
    class Node:
        def __init__(self, key, value, prev=None, next=None):
            self.key = key
            self.value = value
            self.prev = prev
            self.next = next

    def __init__(self):
        self.firstNode = None

    def search(self, key):
        curr = self.firstNode
        while curr is not None:
            if curr.key == key:
                return curr
            curr = curr.next
        return None

    def __setitem__(self, key, value):
        curr = self.search(key)
        if curr is not None:
            curr.value = value
        else:
            new_node = self.Node(key, value)
            if self.firstNode is None:
                self.firstNode = new_node
            else:
                new_node.next = self.firstNode
                self.firstNode.prev = new_node
                self.firstNode = new_node

    def __getitem__(self, key):
        curr = self.search(key)
        if curr is None:
            raise KeyError(f"There was an error with the key '{key}'")
        return curr.value

class dict_binary:
    class Node:
        def __init__(self, key, value, left=None, right=None):
            self.key = key
            self.value = value
            self.left = left
            self.right = right

    def __init__(self):
        self.root = None

    def search(self, curr, key):
        if curr is None or curr.key == key:
            return curr
        elif key < curr.key:
            return self.search(curr.left, key)
        else:
            return self.search(curr.right, key)   

    def insert(self, curr, key, value):
        if key == curr.key:
            curr.value = value
        elif key < curr.key:
            if curr.left is None:
                curr.left = self.Node(key, value)
            else:
                self.insert(curr.left, key, value)
        elif key > curr.key:
            if curr.right is None:
                curr.right = self.Node(key, value)
            else:
                self.insert(curr.right, key, value)

    def __setitem__(self, key, value):
        if self.root is None:
            self.root = self.Node(key, value)
        else:
            self.insert(self.root, key, value)

    def __getitem__(self, key):
        curr = self.search(self.root, key)
        if curr is None:
            raise KeyError(f"There was an error with the key '{key}'")
        return curr.value

问题原因分析 #

1. 测试数据随机性的干扰 #

• 链表实现的查询时间完全取决于键的位置：随机查询时，可能某次命中表头（耗时极短），某次命中表尾（耗时极长），导致单次时间数据波动剧烈。
• 普通二叉搜索树对数据顺序敏感：如果插入的键是有序的（比如连续整数），树会退化成单向链表，复杂度直接降到O(n)，完全偏离预期的O(log n)。

2. 单次测试的系统误差 #

• 单个字典操作的耗时极短，容易受系统调度、后台进程的影响，导致时间数据出现无规律的随机波动。

3. BST实现的先天缺陷 #

• 你的BST没有平衡机制，无法保证树的高度始终为log n，在非随机数据下会迅速失衡，导致性能恶化。

4. 测试场景设计问题 #

• 如果同时混合插入和查询操作，两种操作的复杂度叠加会让时间数据的趋势变得模糊，难以对应到理论复杂度。

优化测试的建议 #

• 控制数据分布：测试BST时使用完全随机的键，避免有序数据；测试链表时，可以固定查询表尾的键，稳定体现O(n)的增长趋势。
• 多次测试取平均：对每个数据规模（如n=100、500、1000...）重复测试100次以上，取平均时间，消除单次测试的随机误差。
• 分离操作测试：分别测试插入和查询的时间，不要混合测试，这样更容易匹配理论复杂度。
• 升级BST实现：将普通BST改为自平衡二叉搜索树（如AVL树、红黑树），才能稳定实现O(log n)的复杂度。

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