算法

算法复杂度

Posted by FanHao on 2020-10-22

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

1
2
3
4
5
6
7
8
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))

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

以下列举了一些实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 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)。具体可点击

循环减半则时间复杂度降为log2**n，代码如下：

1
2
3
4
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$就会令这个算法不能动了，居于中间的几个则差强人意。

FEATURED TAGS
算法
FRIENDS