SortedList.add在内部使用时如何具有o（log（n））时间复杂性？

Question

在sortedContainers中，指定SortedList.add的时间复杂度约为O（log（n）），但我们可以看到它在源代码中使用insort()，即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)的范围内