Median der Mediane in Python läuft nicht in O (n) ⇐ Python

[Anonymous]

Für ein Projekt möchte ich die Laufzeit verschiedener mittlerer Auffindungsalgorithmen vergleichen. Ich begann mit den "Medianen der Median" und verwendete im Grunde genommen den Code, den ich von Geeks für Geeks gefunden habe.

Code: Select all

if __name__ == '__main__':
arr = random.sample(range(1, 10000000000), 10000001)
arr1=arr[:] # i copied the list to make sure they both have the same starting position

t1=time.time()
print("std median", statistics.median(arr))
t2 = time.time()
print("time std median:",t2-t1)
t12 = time.time()
n = len(arr1)
k = n // 2 + 1 #median for odd number of elements
print("Med of Med:", kthSmallest(arr1, 0, n - 1, k))
t21 = time.time()
print("time med of med:", t21-t12)
< /code>
Aus einem unbekannten Grund sind meine Laufzeiten viel und einfach falsch. Das Finden des Medianes in einer Reihe von ~ 10 Mio -Elementen dauerte die folgende Zeit: < /p>
Standard Python method:                  13.28 seconds
My implementation of median of medians:  28.91 seconds
< /code>
Stimmt etwas mit der Implementierung, die ich für Geeks für Geeks gefunden habe, etwas nicht? Es sollte umgekehrt sein. Die Standard -Python -Methode hat eine Laufzeit von O (n log n) 

und Median of Medians läuft in o (n) , daher sollte es schneller sein!>