python 算法

算法的復雜度

算法的時間復雜度是指算法需要消耗的時間資源
時間復雜度用“O（數量級）”來表示
常見的時間復雜度有：
O(1)常數階； 問題規模越大效率越高，時間不變， a = [1,2,3] a[0]＝1，a增加無影響

O(log2n)對數階：問題規模越大效率越高，時間增加慢，

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

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

n代表問題規模
算法中花費的時間與算法中語句的執行次數成正比

空間復雜度 S(n)

一個程序的空間復雜度是指：運行完一個程序所需要內存的大小

數據交換
三個數排序
a=11, b=9, c=8 臨時變量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，手動輸入5個元素，打印出元素為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:")) #手動輸入需要修改為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