Neden benim bisection arama python lineer arama daha yavaş?

Question

Bir görüşme sırasında arama süresinin iyileştirilmesi için ikiye bölme aramasının uygulanması için sorulmuştum ve bununla geldim. Eve geldim ve test ettim ama lineer aramanın büsümden daha iyi bir şekilde yürüdüğü anlaşılıyor. Burada yanlış bir şey mi yaptım?

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 k alıyorsanız dilim uzunluğudur O (k) 'dir. Listeyi split_list() numaralı listede return sorted_list[:half], sorted_list[half:] numaralı satırda tekrarlayın. bisection'a en üst düzey çağrı, tüm listeyenumaralı telefonu çağırır. O (n), sadece split_list'u (sadece sağ yarı boyutunun boyutu = n olduğu için) alır. Doğrusal aramanın zaman karmaşıklığı. Bunu aşmanın

bir yolu (üst düzey çağrı sırasıyla 0 ve len(sorted_list) bir lowerBound ve upperBound kümesi kullanır) fonksiyonunuza özyinelemeli çağrılarda bir lowerBound ve upperBound etrafında geçmek yerine liste dilimleme vardır. Ve length_of_list, upperBound - lowerBound olacaktır.