python算法表示概念扫盲教程

脚本专栏 2024/11/7 佚名

3 2 1

圆月山庄资源网 Design By www.vgjia.com

本文为大家讲解了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,算法表示

圆月山庄资源网 Design By www.vgjia.com

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com

圆月山庄资源网 Design By www.vgjia.com

评论“python算法表示概念扫盲教程”

暂无评论...

P70系列延期，华为新旗舰将在下月发布

3月20日消息，近期博主@数码闲聊站透露，原定三月份发布的华为新旗舰P70系列延期发布，预计4月份上市。

而博主@定焦数码爆料，华为的P70系列在定位上已经超过了Mate60，成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢？
根据目前爆料的消息来看，华为P70系列将推出三个版本，其中P70和P70 Pro采用了三角形的摄像头模组设计，而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智，但辨识度绝对拉满。

更新日志

2024年11月07日

python算法表示概念扫盲教程

python,算法表示

python读写json文件的简单实现

Python实现Mysql数据库连接池实例详解

评论“python算法表示概念扫盲教程”

P70系列延期，华为新旗舰将在下月发布

更新日志

友情链接