Python算法复杂度详解：从常数阶到指数阶

本文旨在深入解析Python算法中的复杂度表示概念，为读者提供清晰的技术参考。

常数阶O(1)

常数，亦称定数，指在运行过程中数值保持不变的常量，与变量相对。

为何下方算法的时间复杂度判定为O(1)而非O(3)？

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的对数，记作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的不断增大，上述时间复杂度随之增加，算法的执行效率逐渐降低。

以上就是本文的全部内容，希望对各位的学习有所帮助，也欢迎大家继续支持本站。