python演算法表示概念掃盲的實例教程

這篇文章主要為大家詳細介紹了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演算法表示概念掃盲的實例教程的詳細內容。更多資訊請關注PHP中文網其他相關文章！