今天，我們來看看直觀地看看我自創(chuàng)算法VS二分查找 的時間、計算量大比拼吧！
二分查找，時間復雜度為O(log2 n)
我的算法，時間復雜度可能為O(logk n)
大家應該知道時間復雜度的效率吧？(不知道？學一學:算法的時間復雜度)
log是對數(shù)，logk n的得數(shù)r滿足k^r=n
所以，log中k越大，得數(shù)越小
這么說，k如果大于2，那我的算法效率應該比二分查找高吧(我的算法默認k=3)
除了數(shù)學計算，我們用@cal_time的方法計算時間
(不知道？看看:時間計算器)
代碼:
from cal_time import *
import time
@cal_time
def twomidsearch(lst,val):
left=0
right=len(lst)-1
count=0
while left<=right:
mid=(left+right)//2
mid1=(left+mid)//2
mid2=(right+mid)//2
if lst[mid1]==val:
return [mid1,count]
if lst[mid2]==val:
return [mid2,count]
if lst[mid1]>val:
right=mid1-1
if lst[mid2]>val:
right=mid2-1
if lst[mid1]<val:
left=mid1+1
if lst[mid2]<val:
left=mid2+1
count+=1
else:
return False
@cal_time
def binary_search(lst,val):
left=0
right=len(lst)-1
count=0
while left<=right: #候選區(qū)有值
mid=(left+right)//2
if lst[mid]==val:
return [mid,count]
elif lst[mid]>val:
right=mid-1
else:
left=mid+1
count+=1
else:
return None
@cal_time
def all_test(max_n):
lst=list(range(1,max_n+1))
for i in range(25):
t=twomidsearch(lst,max_n)
b=binary_search(lst,max_n)
print(t[1])
print(b[1])
max_n=550000000
all_test(max_n)
(電腦性能低的將max_n調(diào)小！目前5.5億，有可能死機！)
運行結(jié)果令我大吃一驚：
twomidsearch run time:0.0012992382049560546875 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0.0099947452545166015625 seconds
15
29
twomidsearch run time:0.0009992122650146484375 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0.003997802734375 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0.0019989013671875 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0.0009992122650146484375 seconds
binary_search run time:0.0059967041015625 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
all_test run time:22.956223964691162109375 seconds
注意第93、94行！
這差距！……厲害厲害
5.5億在計算量最大時，我的算法最少只用了0.0009992122650146484375秒！
所以，下一次在使用有序列表查找時，我覺得我的算法才厲害
今天就給大家講到這里
大家覺得我的算法實用嗎？歡迎評論！
