本文为大家讲解了python算法表示概念,供大家参考,具体内容如下
常数阶O(1)
常数又称定数,是指一个数值不变的常量,与之相反的是变量
为什么下面算法的时间复杂度不是O(3),而是O(1)。
1
2
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句,即:
1
2
3
4
5
6
7
8
9
10
11
12
|
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
对数阶
1
2
3
4
5
|
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)
执行时间随问题规模增长呈正比例增长
1
2
3
4
5
|
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)
1
2
3
4
|
for i in range ( 100 ):
for k in range ( 100 ):
print (i,k)
|
立方阶O(n^3)
k次方阶O(n^k),
指数阶O(2^n)。
随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。