python算法表示概念扫盲教程

yipeiwu_com6年前Python基础

本文为大家讲解了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的不断增大,上述时间复杂度不断增大,算法的执行效率越低。  

 

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

Python中让MySQL查询结果返回字典类型的方法

Python的MySQLdb模块是Python连接MySQL的一个模块,默认查询结果返回是tuple类型,只能通过0,1..等索引下标访问数据 默认连接数据库: 复制代码 代码如下: M...

Python解析并读取PDF文件内容的方法

Python解析并读取PDF文件内容的方法

本文实例讲述了Python解析并读取PDF文件内容的方法。分享给大家供大家参考,具体如下: 一、问题描述 利用python,去读取pdf文本内容。 二、效果 三、运行环境 pytho...

Python+Selenium+phantomjs实现网页模拟登录和截图功能(windows环境)

Python+Selenium+phantomjs实现网页模拟登录和截图功能(windows环境)

本文全部操作均在windows环境下 安装 Python Python是一种跨平台的计算机程序设计语言,它可以运行在Windows、Mac和各种Linux/Unix系统上。是一种面向对象...

python 字典(dict)按键和值排序

python 字典(dict)的特点就是无序的,按照键(key)来提取相应值(value),如果我们需要字典按值排序的话,那可以用下面的方法来进行: 1 下面的是按照value的值从大到...

Python编写的com组件发生R6034错误的原因与解决办法

解决该问题的方法可以为调用本程序的exe文件建立一个合适的manifest文件,指定正确的msvcr90.dll版本即可,具体可参照/post/35219.htm ps:可以使用mt.e...