分析原则

1、 只关注“最坏情况”。

2、 忽略常数和低阶项。 —— 常数的大小本就依赖于具体环境

3、 只能预测趋势。 ——复杂度低不一定耗时少，最坏情况不见得总是出现，粗糙的评判

意义

1、 揭示问题本质上的难易程度。

  • 能够用多项式算法求解的问题 => 易解
  • 只能用指数或阶乘算法求解的问题 => 不易解

2、 粗糙的定量评判也比经验性的定性评判好。

  • 只凭少量实例得到的判断很难得到有价值的结论。

函数增长的渐近记号

Big O

𝒇(𝒏)=𝑶(𝒈(𝒏)),当且仅当：存在大于零的常数𝒄,𝒏0>𝟎，使得对所有的𝒏≥𝒏0，都有𝒇(𝒏)≤𝒄𝒈(𝒏)

1

BigOmega

𝒇(𝒏)=𝛀(𝒈(𝒏)),当且仅当：存在大于零的常数𝒄,𝒏0，使得对所有的𝒏≥𝒏0，都有𝒇(𝒏)≥𝒄𝒈(𝒏)

2

BigTheta

𝒇(𝒏)=𝚯(𝒈(𝒏)),当且仅当：如果存在正数c1，c2和n0，对于所有的n>=n0，有c1*g(n)<=f(n)<=c2*g(n)

3

比较

1、O是一个算法最坏情况的度量(g(n)是这个算法的上界，用上界来衡量，是最坏的情况)

2、Big Omega是最好情况的度量(g(n)是这个算法复杂度的下界，用下界来衡量，是最好的情况)

3、Big Theta表达了一个算法的区间，不会好于某某，不会坏于某某

分析方法

在该课程学习过程中，我们大多数都是以最坏情况来分析算法复杂度的，也就是O。下面给出两种最坏情况的分析方法。

  • 以循环为重点。
  • 循环次数按照最坏情况估计。
  • 循环内的操作次数也按最坏情况估计。
  • 二者相乘即作为分析结果
# 以冒泡排序为例分析Navie分析可行的情况 下面给出python的代码
def bubble_sort(array):
    for i in range(1, len(array)): # 最坏情况为n次
        for j in range(0, len(array)-i): #最坏情况为n次
            if array[j] > array[j+1]:  # 最坏情况为1次
                array[j], array[j+1] = array[j+1], array[j] #最坏情况为1次
    return array

# 复杂度为 O（n^2）
# 以BFS为例分析Navie分析不可行的情况 下面给出BFS的伪码 
# B=所有灰色点构成的集合
# 将所有V中的点标记为白色
# 将s标记为灰色
B.EnQueue(s);
while B非空 # 最多n次
    d=B.DeQueue();
    for d的所有邻居t # 最多m次
        if t的标记为白色
            B.EnQueue(t);
            将t标记为灰色
    将d标记为“黑色”；

# 按Navie分析 复杂度为O(nm)
'''
最坏情况的确是一次循环中检查m条边。但在那种实例下，其他循环岂不是根本不用检查了？'
因此BFS用Navie分析并不合理，不能以循环为重点 而是应该是数据结构也就是BFS维护的队列为核心分析，下面引出聚合分析
''

聚合分析

  • 以数据结构为核心。
  • 将整个程序看作一个总体。
  • 考察数据结构的操作次数。
# 还是以BFS为例分析聚合分析可行的情况 
# B=所有灰色点构成的集合
# 将所有V中的点标记为白色
# 将s标记为灰色
B.EnQueue(s);
while B非空 # 最多n次
    d=B.DeQueue();
    for d的所有邻居t # 最多m次
        if t的标记为白色
            B.EnQueue(t);
            将t标记为灰色
    将d标记为“黑色”；

# 总的入队次数是n；总的出队次数是n 
# 图中一共有m条边；无向图每条边会被检查2次；有向图每条边会被检查1次  
# 按聚合分析 复杂度为O(n+m)
# 分析正确！