Python-Halbierung ist O (n^2)?

Question

ich einen einfachen Test laufen zu überwachen, wie lange dauert es, zu sortieren, setzen Sie in eine Liste mit der bisect Bibliothek

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) 

So nenne ich dies mit:

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

und plotten die Ergebnisse:

ich vermutete, hätte/gehofft, dass insort wo A lle maximal O(nlog(n)) sein. Aus der Dokumentation liest man:

"Denken Sie daran, dass die O (Log n) Suche von der langsamen O (n) -Einfügung Schritt dominiert wird."

Was fehlt mir hier?

EDIT: Mir fehlte etwas sehr offensichtlich. Wie auch immer, ich möchte die Frage mit der gleichen Sache aktualisieren SortedList mit aus dem Paket SortedContainers:

sehr schnell stuff!

Answer 1

bisect ist O (logN). Jedoch ist Einfügen in eine Liste O (N). Du machst das N mal.

Vom bisect.insort_left() documentation:

Beachten Sie, dass der O (log n) Suche ist dominiert durch die langsame O (n) Insertionsschritt.

So Insertion noch O (N), die O (logN) Suchzeit ist (asymptotisch sprechend) unbedeutend im Vergleich zu dem. Also insgesamt, nehmen Ihre zeitgesteuerten Tests N mal O (N) == O (N^2) Zeit.