Python算法效率和增长量级，经典题目回顾

小tips

做这样的分析可以把代码拷贝到记事本，然后在后面写步数，比手写快得多

image.png

第一题

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

上面这个题最好的情形下跑多少步？
当然是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

那上面这个题目在最坏的情况下跑多少步？（我们常常用最坏情况来定义程序复杂度）
那么就需要L是非空列表就好，假定L长度为 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循环取定单个值的时候再分析内部变化
x=n1时，内部y的for循环有n步，对应append命令有2*n步，
那么考虑到x=n1这一步赋值在内
这一次关于x的for循环总步数是1+n+2*n=3*n+1
那么再对这整体乘上n
总循环步数是n*(3*n+1)=3*n^2+n
当然再加上外面的两步赋值就是3*n^2+n+2
证毕

第二题

下面分析步数会更简略地写，有了第一题的基础相信读者看得更明白

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是长为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

同理，太复杂的问题，分析的时候还是取定循环某一环来分析比较缜密！！
x=n1时, 记一步，for y 记n步，if 由于L是全等列表，在for y下记n步，append由于两步在for y 下记2n步
那么当x开始循环

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

加上两步赋值得到
4*n²+n+2

另一种更缜密的思路

x=n1时，

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等长
最好情况，L1与L2全空，显然2步

最糟情况，L2是任意列表，但是L1为全等列表，且L1跟L2的最后一个元素相等，如此能够使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
#最坏情况，步数是n^2+2*n+2

n^2+2*n+2

另外一种考虑复杂度的方法

在每次计算for时，将乘数例如n记录下来
在上面的程序中，"()"括号内的数字是该步自带步数，前面乘数是大循环的乘数，如此计算更快避免错误

考虑渐进复杂度

渐进复杂度是复杂度的最高增长项，可以观察我的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.

那么上面三个程序的渐进复杂度都可以用n^2项来衡量，故上面的渐进复杂度都是O( n²)

最后编辑于：2019.03.31 11:51:54