本文為大家講解了python算法表示概念，供大家參考，具體內(nèi)容如下

常數(shù)階O(1)

常數(shù)又稱定數(shù)，是指一個(gè)數(shù)值不變的常量，與之相反的是變量

為什么下面算法的時(shí)間復(fù)雜度不是O(3)，而是O(1)。

int sum = 0,n = 100; /*執(zhí)行一次*/ 
sum = （1+n）*n/2; /*執(zhí)行一次*/ 
printf（"%d", sum）; /*行次*/

這個(gè)算法的運(yùn)行次數(shù)函數(shù)是f（n）=3。根據(jù)我們推導(dǎo)大O階的方法，第一步就是把常數(shù)項(xiàng)3改為1。在保留最高階項(xiàng)時(shí)發(fā)現(xiàn)，它根本沒有最高階項(xiàng)，所以這個(gè)算法的時(shí)間復(fù)雜度為O(1)。

另外，我們試想一下，如果這個(gè)算法當(dāng)中的語句sum=（1+n）*n/2有10句，即：

int sum = 0, n = 100; /*執(zhí)行1次*/ 
sum = （1+n）*n/2; /*執(zhí)行第1次*/ 
sum = （1+n）*n/2; /*執(zhí)行第2次*/ 
sum = （1+n）*n/2; /*執(zhí)行第3次*/ 
sum = （1+n）*n/2; /*執(zhí)行第4次*/ 
sum = （1+n）*n/2; /*執(zhí)行第5次*/ 
sum = （1+n）*n/2; /*執(zhí)行第6次*/ 
sum = （1+n）*n/2; /*執(zhí)行第7次*/ 
sum = （1+n）*n/2; /*執(zhí)行第8次*/ 
sum = （1+n）*n/2; /*執(zhí)行第9次*/ 
sum = （1+n）*n/2; /*執(zhí)行第10次*/ 
printf（"%d",sum）; /*執(zhí)行1次*/

事實(shí)上無論n為多少，上面的兩段代碼就是3次和12次執(zhí)行的差異。這種與問題的大小無關(guān)（n的多少），執(zhí)行時(shí)間恒定的算法，我們稱之為具有O(1)的時(shí)間復(fù)雜度，又叫常數(shù)階。

注意：不管這個(gè)常數(shù)是多少，我們都記作O(1)，而不能是O(3)、O(12)等其他任何數(shù)字，這是初學(xué)者常常犯的錯(cuò)誤。 

推導(dǎo)大O階方法

1.用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)

2.在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)

3.如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)

對數(shù)階O(log2n)　

對數(shù)

如果a的x次方等于N（a>0，且a不等于1），那么數(shù)x叫做以a為底N的對數(shù)（logarithm），記作x=logaN, 。其中，a叫做對數(shù)的底數(shù)，N叫做真數(shù)。
5^2 = 25 , 記作 2= log5 25
對數(shù)是一種運(yùn)算，與指數(shù)是互逆的運(yùn)算。例如

① 3^2=9 <==> 2=log<3>9；

② 4^(3/2)=8 <==> 3/2=log<4>8；

③ 10^n=35 <==> n=lg35。為了使用方便，人們逐漸把以10為底的常用對數(shù)記作lgN

對數(shù)階

int count = 1; 
while (count < n) 
{  
count = count * 2; /* 時(shí)間復(fù)雜度為O(1)的程序步驟序列 */ 
}

由于每次count乘以2之后，就距離n更近了一分。

也就是說，有多少個(gè)2相乘后大于n，則會退出循環(huán)。

由2^x=n得到x=log2n。所以這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(logn)。 

線性階O(n)　　

執(zhí)行時(shí)間隨問題規(guī)模增長呈正比例增長

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 )

線性對數(shù)階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),
指數(shù)階O(2^n)。

隨著問題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低?！　?/p>

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論