pison bisect is O (n^2)?

Question

Я бегу простой тест, чтобы контролировать, сколько времени потребуется, чтобы сортировать вставить в список с bisect библиотеки

import numpy as np 
import bisect 

def get_time(N): 
    myl = [] 
    a = time.time() 
    for i in np.arange(N): 
     bisect.insort_left(myl, random.randint(0,1000000)) 
    b = time.time() 
    return (b-a) 

Так я называю это с:

t_dict = {} 
for N in [1000,5000,10000,50000,100000,200000,300000,400000,500000]: 
    t_dict[N] = get_time(N) 

и сюжет результаты:

Я предположил бы/надеяться, что insort горе uld должно быть не более O(nlog(n)). Из документации следует, что:

«Имейте в виду, что поиск O (log n) во власти медленного этапа ввода O (n)».

Что мне здесь не хватает?

EDIT: Мне не хватало чего-то чрезвычайно очевидного. Во всяком случае, я хотел бы обновить этот вопрос с теми же вещами, используя SortedList из пакета SortedContainers:

очень быстрый материал!

Answer 1

bisect is O (logN). Однако, вставка в список is O (N). Вы делаете это N раз.

От bisect.insort_left() documentation:

Имейте в виду, что O (журнал N) поиск доминировал на стадии ввода медленно O (п).

Так что вставка по-прежнему O (N), время поиска O (logN) является (асимптотически говоря) несущественным по сравнению с этим. Итак, всего, ваши временные тесты принимают N раз O (N) == O (N^2).