跳转至

算法复杂度分析

既然算法就是解决问题的方法,那么解决同一个问题也就可能会有多种不同的方法,如何评判哪个方法更好,这就需要一个衡量标准。即算法复杂度分析,来找到最优的解决方案。

数据结构和算法本身解决的是“快”和“省”的问题,即如何让代码运行得更快,如何让代码更省存储空间。所以,算法复杂度分析就是分析算法的执行效率以及资源消耗。

  • 快:执行效率,即时间复杂度
  • 省:资源消耗,即空间复杂度

动态分析法

测试结果非常依赖测试环境,比如不同的处理器。另外测试结果受数据规模影响也很大。比如排序算法,如果给一个本身就有序的数据排序,算法可能不需要做任何操作,执行时间会非常短,基本无法判断哪个好哪个坏。

  • time
import time

start_time = time.time()  # 开始时间
pass  # 待测算法
end_time = time.time()  # 结束时间

print(end_time - start_time)  # 耗时
  • timeit
timeit.timeit(stmt, setup,timer, number)
"""
stmt: statement的缩写,要测试的代码或者语句,默认值是"pass"
setup: 在运行stmt前的配置语句,默认值"pass"
timer: 计时器,一般忽略这个参数
number: stmt执行的次数,默认是100万次
"""
# 由于stmt只能是语句,需要借助匿名函数来测试函数
t = timeit.timeit(lambda :range(10), number=500)
print(t)

静态分析法

大O复杂度表示法:O(f(n))

  • 每行代码执行时间:t
  • 数据规模:n
  • 代码总执行次数:f(n)
  • 代码总执行时间:T(n)=f(n)*t

释义:在不运行代码的情况下,假设t相同,n不断增长,忽略常量系数、低阶、底阶等对增长趋势关系不大的部分,复杂度约等于T(n),与f(n)成正比

分析法则

假设每行代码执行的时间都一样,为 unit_time,简写为:t

  • 找循环次数最多的代码段
def test():
  sum = 0  # t
  i = 1  # t
  while i <= n:  # nt
    sum = sum + i  # nt
    i = i + 1  # nt

  return sum

# T(n) = (2+3n)t
# 复杂度:O(n)
  • 找嵌套最多,量级最大的那一段代码
def test():
  sum = 0  # t
  i = 1  # t
  while i <= n:  # nt
    j = 1  # nt
    while j <= n:  # n^2t
      sum = sum + i * j  # n^2t
      j = j + 1  # n^2t

  return sum

# T(n) = (2+2n+3n^2)t
# 复杂度:O(n^2)
  • 若最大有多段则相加,有嵌套则相乘
def f1(n):
  ret = 0
  i = 1
  while i < n:
    ret = ret + f2(i)  # 这里调用了另一个函数f2
    n = n + 1

def f2(n):
  sum = 0
  i = 1
  while i < n:
    sum = sum + i
  return sum

# T(n) = T1(n) * T2(n)
# 复杂度为:O(n^2)

20210406204504

空间复杂度分析

空间复杂度:表示的是代码存储空间随数据规模增长的变化趋势

相对时间复杂度,空间复杂度比较简单,只需掌握最常见的三种即可

时间复杂度分析

时间复杂度,表示的是代码执行效率随数据规模增长的变化趋势

  • 常量级

一般情况下,只要算法中不存在循环或递归语句,无论有多少行代码,都属于常量级,都用O(1)表示

i = 8
j = 6
sum = i + j
  • 对数级

很常见,但通常较难分析

 i=1
 while i <= n:
   i = i * 2

# 退出循环的条件为2^x=n,即要循环x=log2_n次
# 忽略底数之后,复杂度为:O(logn)

上面这段代码循环多少次(x),取决于i,每循环一次i的值要乘2,当循环2^x次后大于n则停止,即x为logn,最终复杂度表示为:O(logn)

如果每循环一次i的值要乘3、乘10等等,忽略底阶后复杂度仍然表示为:O(logn)

如果循环了n次,那就是:O(nlogn)

特殊情况

# 示例1
# 在一个长度不固定的无序列表中,查找元素x所在的位置
# 找到则停止查找,遍历完后没找到则返回-1
def find(_list, x):
  pos = -1
  for i in len(_list):
    if _list[i] == x:
      pos = i
      break
  return pos

在示例1中,要查找的元素x,可能会出现在列表的任意位置,亦或者不在列表中,共有n+1种情况,于是复杂度需要根据不同情况进行分析:

  • 如果x位于首位则时间复杂度为O(1),称之为最好情况时间复杂度
  • 如果x位于末位,则时间复杂度为O(n),称之为最坏情况时间复杂度
  • 但大多数情况下元素都不位于首位或末位,于是我们需要引出平均情况时间复杂度

20211129173852

假设元素x在列表中和不在列表中的概率各自为1/2,如果在列表中,则每个位置的概率相等,均为1/2 * 1/n,即1/2n

总遍历次数,即加权平均值为:(1+2+3+...+n)/2n + n*1/2,前n项和为:n(1+n)/2,最后:T(n)=(3n+1)/4,忽略系数等,最终的平均情况时间复杂度为:O(n)

# 示例2
# 向一个长度为n的列表中插入新数据value,如果列表有剩余空间,则直接插入
# 如果列表没有剩余空间,则先计算其元素总和sum,然后清空列表后将sum插入到列表的首位,再继续插入value
_list = [1,2,3...n]
count = 0
def insert(value):
  if count == len(_list):
    sum = 0
    for i in len(_list):
      sum = sum + _list[i]

    _list.insert(0, sum)
    count = 1

  _list.insert(count, value)
  count = count + 1

在示例2中,根据不同情况分析:

  • 理想的情况下,列表有剩余空间,直接插入即可,即最好情况时间复杂度为O(1)
  • 最坏的情况下,没有剩余空间,需要遍历一次列表求和,所以最坏情况时间复杂度为O(n)
  • 平均情况呢?此处与示例1有所不同

对于示例2来说,列表要么有剩余,要么没有剩余,只有这两种情况,而且有剩余空间的概率远大于没有剩余空间的情况,我们没必要再计算其加权平均值,也就是说绝大多数情况都属于理想的情况,复杂度都是O(1),我们称之为均摊时间复杂度,算是平均情况时间复杂度的一种特殊情况。


最后更新: 2021-11-29