小tips

做這樣的分析可以把代碼拷貝到記事本，然后在后面寫(xiě)步數(shù)，比手寫(xiě)快得多

image.png

第一題

def program1(L):
    multiples = []
    for x in L:
        for y in L:
            multiples.append(x*y)
    return multiples

上面這個(gè)題最好的情形下跑多少步？
當(dāng)然是L為空列表

def program1(L):                 # 0 steps
    multiples = []                    #1 steps
    for x in L:                            #0 steps
        for y in L:                           # 0 steps
            multiples.append(x*y)     # 0 steps
    return multiples              # 1 steps
# total steps in BEST case are   :2 steps

那上面這個(gè)題目在最壞的情況下跑多少步？（我們常常用最壞情況來(lái)定義程序復(fù)雜度）
那么就需要L是非空列表就好，假定L長(zhǎng)度為 n

def program1(L):                 # 0 steps
    multiples = []                    #1 steps
    for x in L:                            #n steps
        for y in L:                           # n*n steps
            multiples.append(x*y)     # 2*n*n steps
    return multiples              # 1 steps
# total steps in WORST case are   :3*n^2+n+2

最壞情況往往難分析一些，但是只需要每次考慮外部for循環(huán)取定單個(gè)值的時(shí)候再分析內(nèi)部變化
x=n1時(shí)，內(nèi)部y的for循環(huán)有n步，對(duì)應(yīng)append命令有2*n步，
那么考慮到x=n1這一步賦值在內(nèi)
這一次關(guān)于x的for循環(huán)總步數(shù)是1+n+2*n=3*n+1
那么再對(duì)這整體乘上n
總循環(huán)步數(shù)是n*(3*n+1)=3*n^2+n
當(dāng)然再加上外面的兩步賦值就是3*n^2+n+2
證畢

第二題

下面分析步數(shù)會(huì)更簡(jiǎn)略地寫(xiě)，有了第一題的基礎(chǔ)相信讀者看得更明白

def program2(L):
    squares = []
    for x in L:
        for y in L:
            if x == y:
                squares.append(x*y)
    return squares

最佳情形下,空列表L

def program2(L):                     # 0
    squares = []                          # 1
    for x in L:                              # 0
        for y in L:                         #0
            if x == y:                        #0
                squares.append(x*y)   #0
    return squares                         #1
#總共是2步

最糟情形下，L是長(zhǎng)為n的非空列表，而且，L的所有元素相同！

def program2(L):                     # 0
    squares = []                          # 1
    for x in L:                              # n
        for y in L:                         # n*n
            if x == y:                        #   n*n
                squares.append(x*y)   #   2*n*n
    return squares                         #1
#總共是   1+n+4*n^2+1=4*n^2+n+2

同理，太復(fù)雜的問(wèn)題，分析的時(shí)候還是取定循環(huán)某一環(huán)來(lái)分析比較縝密??！
x=n1時(shí), 記一步，for y 記n步，if 由于L是全等列表，在for y下記n步，append由于兩步在for y 下記2n步
那么當(dāng)x開(kāi)始循環(huán)

記n(1+n+n+2n)=4n²+n

加上兩步賦值得到
4*n²+n+2

另一種更縝密的思路

x=n1時(shí)，

y=n2記一步
if記一步，由于全等序列L
append記兩步
for y 下總共記 n(2+1+1)=4n步
x=n1記一步，在
for x下總共記 n(4n+1)=4*n²+n步

第三題

def program3(L1, L2):
    intersection = []
    for elt in L1:
        if elt in L2:
            intersection.append(elt)
    return intersection

這里假定 L1與L2等長(zhǎng)
最好情況，L1與L2全空，顯然2步

最糟情況，L2是任意列表，但是L1為全等列表，且L1跟L2的最后一個(gè)元素相等，如此能夠使if檢查到L2最后

def program3(L1, L2):
    intersection = []                  # 1
    for elt in L1:                         #n
        if elt in L2:                      #n*(n)
            intersection.append(elt)        #n*(1)
    return intersection          #1
#最壞情況，步數(shù)是n^2+2*n+2

n^2+2*n+2

另外一種考慮復(fù)雜度的方法

在每次計(jì)算for時(shí)，將乘數(shù)例如n記錄下來(lái)
在上面的程序中，"()"括號(hào)內(nèi)的數(shù)字是該步自帶步數(shù)，前面乘數(shù)是大循環(huán)的乘數(shù)，如此計(jì)算更快避免錯(cuò)誤

考慮漸進(jìn)復(fù)雜度

漸進(jìn)復(fù)雜度是復(fù)雜度的最高增長(zhǎng)項(xiàng)，可以觀察我的CSDN博客
https://blog.csdn.net/weixin_41593821/article/details/88762533

the idea of “asymptotic complexity”, which means we describe running time in terms of number of basic steps. We’ve described the best- and worst-case running times in terms number of basic steps for the three programs above. Now, we’d like you to give the complexity order (ie, “Big O” running time) of each of the above programs.

那么上面三個(gè)程序的漸進(jìn)復(fù)雜度都可以用n^2項(xiàng)來(lái)衡量，故上面的漸進(jìn)復(fù)雜度都是O( n²)