python算法表示概念扫盲教程
作者:金角大王 发布时间:2022-06-22 00:43:34
本文为大家讲解了python算法表示概念,供大家参考,具体内容如下
常数阶O(1)
常数又称定数,是指一个数值不变的常量,与之相反的是变量
为什么下面算法的时间复杂度不是O(3),而是O(1)。
int sum = 0,n = 100; /*执行一次*/
sum = (1+n)*n/2; /*执行一次*/
printf("%d", sum); /*行次*/
这个算法的运行次数函数是f(n)=3。根据我们推导大O阶的方法,第一步就是把常数项3改为1。在保留最高阶项时发现,它根本没有最高阶项,所以这个算法的时间复杂度为O(1)。
另外,我们试想一下,如果这个算法当中的语句sum=(1+n)*n/2有10句,即:
int sum = 0, n = 100; /*执行1次*/
sum = (1+n)*n/2; /*执行第1次*/
sum = (1+n)*n/2; /*执行第2次*/
sum = (1+n)*n/2; /*执行第3次*/
sum = (1+n)*n/2; /*执行第4次*/
sum = (1+n)*n/2; /*执行第5次*/
sum = (1+n)*n/2; /*执行第6次*/
sum = (1+n)*n/2; /*执行第7次*/
sum = (1+n)*n/2; /*执行第8次*/
sum = (1+n)*n/2; /*执行第9次*/
sum = (1+n)*n/2; /*执行第10次*/
printf("%d",sum); /*执行1次*/
事实上无论n为多少,上面的两段代码就是3次和12次执行的差异。这种与问题的大小无关(n的多少),执行时间恒定的算法,我们称之为具有O(1)的时间复杂度,又叫常数阶。
注意:不管这个常数是多少,我们都记作O(1),而不能是O(3)、O(12)等其他任何数字,这是初学者常常犯的错误。
推导大O阶方法
1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数函数中,只保留最高阶项
3.如果最高阶项存在且不是1,则去除与这个项相乘的常数
对数阶O(log2n)
对数
如果a的x次方等于N(a>0,且a不等于1),那么数x叫做以a为底N的对数(logarithm),记作x=logaN, 。其中,a叫做对数的底数,N叫做真数。
5^2 = 25 , 记作 2= log5 25
对数是一种运算,与指数是互逆的运算。例如
① 3^2=9 <==> 2=log<3>9;
② 4^(3/2)=8 <==> 3/2=log<4>8;
③ 10^n=35 <==> n=lg35。为了使用方便,人们逐渐把以10为底的常用对数记作lgN
对数阶
int count = 1;
while (count < n)
{
count = count * 2; /* 时间复杂度为O(1)的程序步骤序列 */
}
由于每次count乘以2之后,就距离n更近了一分。
也就是说,有多少个2相乘后大于n,则会退出循环。
由2^x=n得到x=log2n。所以这个循环的时间复杂度为O(logn)。
线性阶O(n)
执行时间随问题规模增长呈正比例增长
data = [ 8,3,67,77,78,22,6,3,88,21,2]
find_num = 22
for i in data:
if i == 22:
print("find",find_num,i )
线性对数阶O(nlog2n)
平方阶O(n^2)
for i in range(100):
for k in range(100):
print(i,k)
立方阶O(n^3)
k次方阶O(n^k),
指数阶O(2^n)。
随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。


猜你喜欢
- 背景介绍Pandas的DataFrame和Series在Matplotlib基础上封装了一个简易的绘图函数,使得数据处理过程中方便可视化查看
- 前言:上一篇博客我用AOP+AbstractRoutingDataSource实现了MySQL读写分离,自己写代码实现判断该使用哪个数据源挺
- 最近由于公司有一个向谷歌网站上传文件的需求,需要进行web的自动化测试,选择了selenium这个自动化测试框架,以前没有接触过这门技术,所
- 今天天气"刚刚好"(薛之谦么么哒),无聊的我翻到了一篇关于csv文件读取与写入的帖子,作为测试小白的我一直对python
- 使用sql的计划任务可以处理一些特殊环境的数据,除了使用windows系统的计划任务来定时处理,不过要配合程序才行,有些事情可以直接使用sq
- 一旦你创建一个 Template 对象,你可以用 context 来传递数据给它。 一个context是一系列变量和它们值的集合。conte
- 背景:周末归纳下mysql的日志文件,其中general_log在mysql入侵中已经用到过,binlog即将会用到。注:mysql版本为5
- 前言公司的Ubuntu服务器对于各个系统的目录是放在不同的逻辑分区上的,比如存放mysql数据库文件的默认目录/var/lib/mysql所
- 导 读vue3.0中,响应式数据部分弃用了 Object.defineProperty ,使用 Proxy 来代替它。本文将主要通过以下方面
- 这篇文章主要介绍了Python3打包exe代码2种方法实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,
- 本文实例讲述了PHP+Ajax实现无刷新分页的方法。分享给大家供大家参考,具体如下:注:这里使用到的一些类库在前面文章都能找到源代码,因此为
- 直接分析,如原矩阵如下(1): (1) 我们要截取的矩阵(取其一三行,和三四列数据构成矩阵)为如下(2): (2)错
- 0x00 前言eval是Python用于执行python表达式的一个内置函数,使用eval,可以很方便的将字符串动态执行。比如下列代码:&g
- UEditor效果图一、简介UEditor是一个开源免费的编辑器,由百度web前端研发部开发所见即所得富文本web编辑器,具有轻量,可定制,
- 一、引用返回引用返回用在当想用函数找到引用应该被绑定在哪一个变量上面时。不要用返回引用来增加性能,引擎足够聪明来自己进行优化。仅在有合理的技
- 没什么实际用途,纯属消遣Quick Click<html><head><title>Quick_Clic
- 这篇日志完全是看了一篇日志后的启发,原文为: * 的eval和new Function。很少使用new Array的方式来定义数组,没想到ne
- python格式化字符串有%和{}两种 字符串格式控制符.字符串输入数据格式类型(%格式操作符号)%%百分号标记#就是输出一个%%c字符及其
- 本文实例讲述了Python开发的实用计算器。分享给大家供大家参考,具体如下:实现功能:图形界面PyQt,输入框,+,—,*,/ ;乘方 ,开
- 一、连接Go语言中的database/sql包提供了保证SQL或类SQL数据库的泛用接口,并不提供具体的数据库驱动。使用database/s