python - SortedList.add 在内部使用 insort 时如何具有 o(log(n)) 时间复杂度？

Question

在 sortedContainers 中指定 SortedList.add 具有大约 O(log(n)) 的时间复杂度，但我们可以看到它在源代码，O(n):

    def add(self, value):
        """Add `value` to sorted list.
        Runtime complexity: `O(log(n))` -- approximate.
        >>> sl = SortedList()
        >>> sl.add(3)
        >>> sl.add(1)
        >>> sl.add(2)
        >>> sl
        SortedList([1, 2, 3])
        :param value: value to add to sorted list
        """
        _lists = self._lists
        _maxes = self._maxes

        if _maxes:
            pos = bisect_right(_maxes, value)

            if pos == len(_maxes):
                pos -= 1
                _lists[pos].append(value)
                _maxes[pos] = value
            else:
                insort(_lists[pos], value)

            self._expand(pos)
        else:
            _lists.append([value])
            _maxes.append(value)

        self._len += 1

有人可以解释为什么尽管使用了 insort ，该方法仍然近似于 O(log(n)) 吗？

Answer 1

好的，从我在代码中看到的，SortedList 使用一组列表来存储排序后的列表。 add 首先找到相关的子列表，然后用insort 插入其中，所以它在子列表的长度上是线性的，而不是整个列表。我怀疑 SortedList 试图保持每个子列表的长度受 log(whole list) 限制。