您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

Python查找算法之我的算法VS二分查找,真正的差之毫厘谬以千里

时间:2021-08-17 10:10:24  来源:  作者:阿尔法Yang

今天,我们来看看直观地看看我自创算法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秒!

所以,下一次在使用有序列表查找时,我觉得我的算法才厉害

今天就给大家讲到这里

大家觉得我的算法实用吗?欢迎评论!



Tags:Python查找算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
今天,我们来看看直观地看看我自创算法VS二分查找 的时间、计算量大比拼吧!二分查找,时间复杂度为O(log2 n)我的算法,时间复杂度可能为O(logk n)大家应该知道时间复杂度的效率吧?(...【详细内容】
2021-08-17  Tags: Python查找算法  点击:(119)  评论:(0)  加入收藏
▌简易百科推荐
背景对抗是反作弊永恒的主旋律,面对对抗我们需要做到快速响应、见招拆招、在变化中发现不变的本质。在反作弊场景中,黑产必须通过文本进行信息传递或触达受害者,而文本由于其生...【详细内容】
2022-07-14  字节跳动技术团队    Tags:算法   点击:(4)  评论:(0)  加入收藏
请实现一个函数用来匹配包含&#39;. &#39;和&#39;*&#39;的正则表达式。模式中的字符&#39;.&#39;表示任意一个字符,而&#39;*&#39;表示它前面的字符可以出现任意次(含0次)。在本题...【详细内容】
2022-07-13  做架构师不做框架师    Tags:正则表达式   点击:(6)  评论:(0)  加入收藏
高手:滑动窗口是一种比较常用的数据统计算法。简单来说,就是在一个大的数组上,定义一个固定长度的滑动窗口,然后这个窗口在数组上进行滑动。在窗口滑动的过程中,左边会出一个元素...【详细内容】
2022-07-13  跟着Mic学架构    Tags:算法   点击:(8)  评论:(0)  加入收藏
一、希尔排序介绍希尔排序这个名字,来源于它的发明者希尔,也称作“缩小增量排序”,是插入排序的一种更高效的改进版本。希尔排序是基于插入排序的以下两点性质而提出改进方法的...【详细内容】
2022-07-08  程序猿星球    Tags:希尔排序   点击:(14)  评论:(0)  加入收藏
描述为了保证第三方应用与API服务器之间通信的安全性,防止Secret Key盗用、数据篡改等恶意攻击行为,开放平台API 服务器使用签名机制,应用在调用开放平台API,需要计算出一个签...【详细内容】
2022-07-08  零一间    Tags:算法   点击:(9)  评论:(0)  加入收藏
6. 蒙特卡洛算法6.1 计算&pi;" role="presentation" style="display: inline; font-style: normal; font-weight: normal; text-indent: 0px; text-align: left; text-trans...【详细内容】
2022-07-08  海椰人  博客园  Tags:算法   点击:(17)  评论:(0)  加入收藏
数学统计在我们的程序当中特别是数据分析当中是必不可少的一部分,本文就来介绍一下 NumPy 常见的统计函数。最大值与最小值numpy.amin()用于计算数组中的元素沿指定轴的最小...【详细内容】
2022-07-07  VT漫步    Tags:统计函数   点击:(15)  评论:(0)  加入收藏
一、基础概念1、Sorted(单调递增or单调递减)2、Bounded(存在上下界)3、Accessible by index(能够通过索引访问,数组适合,but链表不适合)二分查找是一种在每次比较之后将查找空间一...【详细内容】
2022-07-04  程序猿星球    Tags:算法   点击:(14)  评论:(0)  加入收藏
分布式系统的模型为了更容易理解分布式系统,我们先来构建一个模型。 武当派因为人口增长变成 11 个办事处分散在地图各地; 办事处之间的通信只能依靠信鸽; 一只信鸽可能无法完...【详细内容】
2022-07-01  算法的秘密    Tags:共识算法   点击:(20)  评论:(0)  加入收藏
在本课程中, 您将 详细、逐步地解释经典的精选 LeetCode 问题 ,您将了解解决技术编码面试问题的最佳方法。 这是我在准备面试时希望参加的课程。课程英文名:LeetCode in Java A...【详细内容】
2022-06-30  IT教程精选    Tags:LeetCode   点击:(19)  评论:(0)  加入收藏
相关文章
    无相关信息
站内最新
站内热门
站内头条