SortedList.add 在内部使用 insort 时，怎么会有 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).

限制

SortedList.add 在内部使用 insort 时，怎么会有 o(log(n)) 的时间复杂度？

How can SortedList.add have o(log(n)) time complexity when it uses insort internally?

python

sortedcontainers