今天,我们来看看直观地看看我自创算法VS二分查找 的时间、计算量大比拼吧!
二分查找,时间复杂度为O(log2 n)
我的算法,时间复杂度可能为O(logk n)
大家应该知道时间复杂度的效率吧?(不知道?学一学:算法的时间复杂度)
log是对数,logk n的得数r满足k^r=n
所以,log中k越大,得数越小
这么说,k如果大于2,那我的算法效率应该比二分查找高吧(我的算法默认k=3)
除了数学计算,我们用@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: #候选区有值
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调小!目前5.5亿,有可能死机!)
运行结果令我大吃一惊:
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秒!
所以,下一次在使用有序列表查找时,我觉得我的算法才厉害
今天就给大家讲到这里
大家觉得我的算法实用吗?欢迎评论!