分析算法的好坏主要是从计算机资源消耗的角度来评判的

如果一个算法能更高效的利用计算资源，或者更少的占用计算机资源就是更好的算法。

这里说的计算机资源是指：
1.存储空间(内存空间和辅存空间)
2.执行时间

如果要测试一个算法，请在一台机器上运行，因为一个相同的算法，放在不能性能的机器上运行得到的运行时间是不同的。

====================

大O表示法

大O表示法是用于衡量算法运行时间的。

怎么衡量一个算法的运行时间，或者说是什么使得一个算法的运行时间增加？
答案是赋值语句的数量。

一条赋值语句包含了(表达式)计算和(变量)存储这两个基本资源。
里面的计算就会消耗CPU资源，会消耗时间；
里面的存储就会消耗内存资源，会消耗空间；

例如一个累加的计算,我用两种算法实现

def sumOfN(n):
    res = 0
    for i in range(1,1+n):
        res+=i 
    
    return res
    
def sumofN2(n):
    res=0
    res = (n+1)*n/2
    return res 

    
假如我传入n=1000

此时算法1的赋值语句一共有 n+1 条
而  算法2的赋值语句只有 2 条

所以 算法1赋值语句数量用 T(n)=1+n 表示
     算法2赋值语句数量用 T(n)=2   表示
     

另一个概念 ：问题规模
什么是问题规模，问题规模就是 n 。说更直白一点就是 上面的两个函数 我如果将 n=1000 改为 n=10000 那么就是将问题规模扩大。

算法分析的目标就是找出问题规模n会怎么影响一个算法的执行时间T(n)。
例如：算法1中，随着n的增大，T(n)会线性的增大
      算法2中，随着n的增大，T(n)不会增大
      
问题规模是影响运行时间的主导因素

除了问题规模，具体数据也是运行时间的影响因素
举个例子：
排序
如果我给一个完全打乱的数据集排序，和给一个只有一两个数是打乱的数据集排序，两个数据集的数据个数相同。此时用相同的算法排序后者会快于前者。

所以在实际测试中，我们应该设置多组数据，并且以多组数据的平均值作为比较的指标

大O表示法：
我们比较算法的好坏实际上不是看 T(n) 的值，而是看 T(n) 中起决定因素的主导部分。这个部分我们称之为 “数量级函数”，这个主导部分具体是什么？是T(n)中随着n增加而增加的最快的部分。

举例：
T(n)=1+n 
随着n增大，常数1会显得无足轻重，n才是主要部分，所以运行时间数量级是 O(n)

T(n)=5n^2+27n+1005
随着n增加，n^2的增长速度会越来越快，而27n+1005影响不大，系数5也是。所以主导部分是n^2 
数量级(函数)是 O(n^2)

也就是说：
数量级函数就是 T(n)中导数最大的那一项再去掉系数

下面是最常见的数量级

O(1)
O(logn)
O(n)
O(n*logn)
O(n^2)
O(n^3)
O(2^n)

上面7个数量级依次增加下面我们具体计算一个代码的时间复杂度

a=5
b=6
c=10    # 3次

for i in range(n):
    for j in range(n):
        x=i*i
        y=j*j 
        z=j*i               #3*n^2 次
        
for k in range(n):          
    w = a*k+45
    v = b*b                 # 2*n次

d=33        # 1次

所以 T(n) = 3n^2+2n+4 , O(n) = n^2

总结：
使用程序运行的时间衡量算法的好坏，而程序运行的时间由代码中赋值语句条数T(n)决定。
运行的时间由问题规模和具体数据决定，问题规模n是主要因素
现实中，使用T(n)中的主导部分O(xx)来表示时间复杂度，而不是T(n)本身。

================================

变位词判断问题

这样的词是变位词：长度相等，字母相同，排列顺序不同。
例如 heart earth ； python typhon 

接下来要使用4中算法来判断两个词是否为变位词

# 算法1：逐字检查法
# T(n)=(n+1)n/2  复杂度为 O(n^2)

def solution1(s1,s2):
    pos1 = 0
    s2 = list(s2)
    real_found = True
    while pos1<len(s1) and real_found:
        pos2 = 0
        found = False
        while pos2<len(s2) and not found:
            if s1[pos1] == s2[pos2]:
                s2[pos2] = None
                found = True
            else:
                pos2 += 1
        if not found:
            real_found = False

        pos1+=1

    return real_found

 

# 算法2：排序比较，即将两个单词按字母排序，之后再注意比较
# 复杂度为 O(nlogn),数量级的主导部分在sort()排序里面，sort后面的for循环复杂度为 n < nlogn ,所以复杂度为 O(nlogn)而不是O(n)

def solution2(s1,s2):
    len1 = len(s1)
    len2 = len(s2)

    if len1 != len2:
        return False

    s1 = list(s1)
    s2 = list(s2)
    s1.sort()
    s2.sort()

    for i in range(len1):
        if s1[i]!=s2[i]:
            return False

    return True

 

# 算法3：暴力法
# 列出s1所有字母能组成的单词的排列组合放到一个列表中
# 再循环判断s2是不是在 s1的字母组成的单词列表中
# 复杂度为 O(n!) 即n阶乘，它的数量级比2^n还要大

 

# 算法4：计数比较法，将单词的每个字母做一个计数器，将s1的计数器和s2的计数器进行比较
# T(n) = 2n+26 , 复杂度为 O(n)

def solution4(s1,s2):
    if len(s1) != len(s2):
        return False

    count1 = [0]*26
    count2 = [0]*26

    for alpha in s1:
        index = ord(alpha) - ord("a")
        count1[index]+=1

    for alpha in s2:
        index = ord(alpha) - ord("a")
        count2[index] += 1

    for i in range(len(count1)):
        if count1[i]!=count2[i]:
            return False

    return True

if __name__=="__main__":
    s1="python"
    s2="typhon"
    print(solution1(s1,s2))
    print(solution2(s1,s2))
    print(solution4(s1,s2))

  
综上：算法4复杂度最小，性能最优。
但是，注意观察，算法4使用了26长度的列表来保存计数器。是牺牲了存储空间换来的运算时间。

所以在算法中，经常会出现这种时间空间之间的取舍问题。

=====================================

python中两种内置数据类型list和dict的大O数量级

先说列表：
v=a[i] 或者 a[i]=v   -> O(1)
a.append(x)         -> O(1)    
list2 = list1 + [1,2,3]  -> O(n+k)

pop()       -> O(1)
pop(1)      -> O(n)

为什么pop传参和不传参它的复杂度不同？
原因是：pop(n) 需要将被移除元素后面的元素全部往前挪位复制一遍。
这个方法看起来很笨，但是他可以保证列表按索引取值赋值(a[i]=v, v=a[i])操作达到O(i)。
所以其实他是为了降低不常用操作的性能来提高常用操作的性能。

判断一个值是否在list中 （如 if v in list1） 性能是 O(n)

字典和列表不同，是根据关键码key 找到数据项，而列表式根据位置 index
对于字典而言，赋值和取值性能为 O(1)
而判断一个key是否在字典中（如 if k in dict1或者contains方法）性能也是O(1)