python 算法

算法的復(fù)雜度

算法的時(shí)間復(fù)雜度是指算法需要消耗的時(shí)間資源
時(shí)間復(fù)雜度用“O（數(shù)量級(jí)）”來(lái)表示
常見(jiàn)的時(shí)間復(fù)雜度有：
O(1)常數(shù)階； 問(wèn)題規(guī)模越大效率越高，時(shí)間不變， a = [1,2,3] a[0]＝1，a增加無(wú)影響

O(log2n)對(duì)數(shù)階：?jiǎn)栴}規(guī)模越大效率越高，時(shí)間增加慢，

O(n)：線性階，時(shí)間隨數(shù)據(jù)規(guī)模增加，線性增加，時(shí)間增加正常 , 例子：for i in range(n)

O(n2)：平方階，時(shí)間隨數(shù)據(jù)規(guī)模增加，指數(shù)增加，時(shí)間增加快 ，for i in range(n): for j in range(i):........

n代表問(wèn)題規(guī)模
算法中花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比

空間復(fù)雜度 S(n)

一個(gè)程序的空間復(fù)雜度是指：運(yùn)行完一個(gè)程序所需要內(nèi)存的大小

數(shù)據(jù)交換
三個(gè)數(shù)排序
a=11, b=9, c=8 臨時(shí)變量t

[root@133 ~]# vim change.py      
#!/usr/bin/python

def swap(a,b,c):
    if  a > b:
        t = a
        a = b
        b = t
    if  a > c:
        t = a
        a = c
        c = t
    if  b > c:
        t = b
        b = c
        c = t
    print  a,b,c

if name == 'main':
swap(11,9,8)

例子2：list A全部為0，修改部分列表元素為1，手動(dòng)輸入5個(gè)元素，打印出元素為0的元素位置

[root@133 ~]# vim key.py   
#!/usr/bin/python
#encoding:utf8
def key():
    a = []
    for i in  range(10):
        a.append(0)   #a=[0,0,0,0,0,0,0,0,0,0]
    for i in range(5):
        input = int(raw_input("Please input a num:")) #手動(dòng)輸入需要修改為1的列表元素
        a[input] = 1 # a[4]=1
    for i in range(len(a)):
        if a[i] == 0:
            print i

if __name__ == '__main__':
    key()
~                      

[root@133 ~]# python key.py
Please input a num:1
Please input a num:2
Please input a num:3
Please input a num:4
Please input a num:5
0
6
7
8
9