算法复杂度计算

Question

在 LeetCode 上刷题，碰到一个题目，涉及时间复杂度的概念，如下。为了了解 O(n) 这个概念，后面去学习了时间复杂度相关内容。

76. 最小覆盖子串
给你一个字符串 S、一个字符串 T。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。 

示例：输入：S = "ADOBECODEBANC", T = "ABC“
             输出："BANC" 

提示：如果 S 中不存这样的子串，则返回空字符串 ""。
     如果 S 中存在这样的子串，我们保证它是唯一的答案。

概念

首先算法复杂度是衡量算法好坏的一个重要指标。其次对算法的分析是通过预估分析得到，而不是将以该算法编写的程序上机运行，统计程序运行时间。

程序执行时间受运行环境和输入规模的影响，代码绝对执行时间无法估计。有时候这种统计甚至会掩盖算法本身的优劣。算法时间复杂度采用预估分析方法！

预估分析法

比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。

非精确计算出算法的运行时间，而是用统计方法分析出不同算法的花费时间长短。

主要分析代码的基本操作的执行次数。而算法花费时间与代码基本操作执行次数成正比。

T(n) 与 O(n)

（1）时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。

（2）n 的含义：n 被称为问题的规模，当 n 变化时，T(n) 也不断变化。当我们想了解 T(n) 与 n 之间的变化规律时，此时引入一个新的概念——时间复杂度。

（3）时间复杂度：算法中基本操作重复执行的次数是问题规模 n 的某个函数，用 T(n) 表示，若有某个辅助函数 f(n),使得当 n 趋近于无穷大时，T(n)/f(n) 的极限值为不等于零的常数，则称 f(n) 是 T(n) 的同数量级函数。记作 T(n)=Ｏ(f(n))，而称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度，用大写 O 表示。

推导 O(n)

分析 T(n)

分析由算法编写得到的代码可参考几个原则

• O(1):适用输入输出语句、赋值语句、判断 if/else 语句、选择结构
• 求和法则：适用常规语句，顺序结构

  T1(n)=O(f(n)) 和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))
  T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))

• 乘法法则：适用循环结构

  T1(n)=O(f(n)) 和 T2(n)=O(g(n)),则 T1T2=O(f(n)g(n))

• 复杂算法可分解成比较容易估算的几个部分。

以下列举了一些实例

# O(1)
# 注意：如果算法的执行时间不随着问题规模 n 的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是 O(1)。
a='O1'
print(a)

# O(n)
# python 代码中对 list、set、str 等类型数据的部分操作为 O(n)
i=0
while i<n:
    i+=1

# O(log2n),以 2 为底数的对数
i=1
while i<n:
    i=i*2

n = 64
while n > 1:
    print(n)
    n = n // 2      # 循环减半
    
# O(n^2)，双重嵌套循环，同理 O(n^3)
i=0；                 zzz 
while i<n:
    for j in list1:         # 执行 n^2 次
         val = list1[i]+j   # 执行 n^2 次
	i+=1

注意

Python 语法中对列表、集合、字符串、字典的部分操作时间复杂度为 $O(n)$。具体可 点击

循环减半则时间复杂度降为 $log2n$，代码如下：

n = 64
while n>1:
    print(n)
    n = n//2

推导 O((fn))

根据前面的概念。T(n)=O(f(n))，而 O(f(n)) 为时间复杂度。可以根据 T(n) 推导出 O(n)

推导时间复杂度 O(f(n))，有如下几个原则：

• 如果运行时间是常数量级，用常数 1 表示；
• 只保留时间函数中的最高阶项；
• 如果最高阶项存在，则省去最高阶项前面的系数。

具体看几个实例规则:

1、$T(n) = 3n$，则 $T(n)=O(n)$; 时间复杂度 $O(n)$

2、$T(n) = 3$，则 $T(n)=O(1)$; 时间复杂度 $O(1)$

3、$T(n) = 5log_2n$ ，则 $T(n)=O(log_2n)$；时间复杂度 $O(log_2n)$

4、$T(n) = 3n^2$，则 $T(n)=O(n^2)$; 时间复杂度 $O(n^2)$

$$O(2n^2+n+1) = O(3n^2+n+3) = O(7n^2+n) = O(n^2)$$

总结

常见时间复杂度

常数阶 $Ο(1)$、 对数阶 $Ο(log_2n)$、线性阶 $O(n)$、 线性对数阶 $O(nlog_2n)$、平方阶 $O(n^2)$，立方阶 $O(n^3)$、…， k 次方阶 $O(n^k)$，指数阶 $O(2^n)$。随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

经验规则

$Ο(1)＜Ο(log_2n)＜Ο(n)＜Ο(nlog_2n)＜Ο(n^2)＜Ο(n^3)＜…＜Ο(2^n)＜Ο(n!)$
如果一个算法的复杂度为$c$ 、 $log_2n$ 、$n$、$nlog_2n$，那么这个算法时间效率比较高，如果是 $2^n$ 、$3^n$ 、$n!$，那么稍微大一些的 $n$ 就会令这个算法不能动了，居于中间的几个则差强人意。