Perché la mia ricerca di bisezione è più lenta della ricerca lineare in python?

Question

Durante un'intervista mi è stato chiesto di implementare la ricerca di bisezione per migliorare i tempi di ricerca e mi è venuto in mente questo. Sono tornato a casa e lo ho testato, ma sembra che la ricerca lineare stia facendo molto meglio della mia ricerca in bisezione. Ho fatto qualcosa di sbagliato qui?

import time 

sorted_list = range(0, 10000000) 
needle = 9999999 

def split_list(sorted_list): 
    half = len(sorted_list)/2 
    return sorted_list[:half], sorted_list[half:] 

def bisection(haystack, needle, length_of_list): 
    if len(haystack) <= length_of_list/5: 
     return haystack 

    first, last = split_list(haystack) 
    if needle < first[-1]: 
     return bisection(first, needle, length_of_list) 
    else: 
     return bisection(last, needle, length_of_list) 

def linear_search(smaller_ist): 
    for ele in smaller_list: 
     if ele == needle: 
      return 0 

start_time = time.time() 
smaller_list = bisection(sorted_list, needle, len(sorted_list)) 
print linear_search(smaller_list) 
print("--- %s seconds ---" % (time.time() - start_time)) 

start_time = time.time() 
print linear_search(sorted_list) 
print("--- %s seconds ---" % (time.time() - start_time)) 

Answer 1

List slicing è O (k) dove k è la lunghezza della fetta si stanno ottenendo. È possibile suddividere ripetutamente l'elenco in split_list(), nella riga return sorted_list[:half], sorted_list[half:]. La chiamata di livello superiore a bisection, che chiama split_list() nell'intero elenco, impiegherà O (n) solo per eseguire split_list (poiché la dimensione della metà sinistra + la dimensione della metà destra = n), che di per sé corrisponde già al complessità temporale della ricerca lineare.

Un modo per aggirare il problema è, invece di lista affettare, passare intorno ad un lowerBound e upperBound nelle chiamate ricorsive alla funzione (dove la chiamata di livello superiore utilizza rispettivamente un set lowerBound e upperBound-0 e len(sorted_list)). E length_of_list sarebbe upperBound - lowerBound.