复杂度分析
Varsion

大O复杂度表示法

所有代码的执行时间 T(n) 与每行代码的执行次数

1
2
3
4
5
6
7
def cal (n)
sum = 0
for i in 1..nu
sum += i
end
return sum
end

粗略估计该方法的时间复杂度:

将每行代码的执行时间都设为 1u ,第2行代码需要 1u ,第3,4代码(for循环)运行了N次,这段代码的总执行时间就是(2n+1)*u

我们可以得出,所有代码的执行时间T(n)与每行代码的执行次数成正比

1
2
3
4
5
6
7
8
9
10
def cal(n)
sum = 0
for i in 0..n
j = 1
for j in 0..n
sum = sum + i*j
end
end
return sum
end

再看一下该函数

同样假设每行代码的执行时间都为 1u ,第2行需要1u ,第3,4行执行N次也就是 2n*u,第5,6行执行了 次,所以整段代码执行的总时间为:(2n²+2n+1)*u

通过这两段代码可以推出一个重要结论:

所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比

T(n) = O(f(n))

  • T(n)表示代码执行的时间;
  • n 表示数据规模的大小;
  • f(n) 表示每行代码执行的次数总和。
  • 因为这是一个公式,所以用 f(n) 来表示。公式中的 O,表示代码的执行时间 T(n)f(n) 表达式成正比。

大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度

当N的数量级很大的时候,公式中的常数、系数和低阶表达式都是可以忽略的,只需要考虑最大量级即可,随意刚刚的两个表达式也可以写为T(n) = O(n), T(n) = O(n²)

时间复杂度分析

只关注循环执行次数最多的一段代码

我们通常会忽略掉公式中的常量、低阶、系数,只需要记录一个最大阶的量级就可以了。所以,我们在分析一个算法、一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 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
28
def cal(int n) 
# yield 1
sum_1 = 0
p = 1
for p in 0..100
sum_1 = sum_1 + p
end

# yield 2
sum_2 = 0
q = 1
for q in 0..n
sum_2 = sum_2 + q
end

# yield 3
sum_3 = 0
i = 1
j = 1
for i in i..n
j = 1;
for j in j..n
sum_3 = sum_3 + i * j
end
end

return sum_1 + sum_2 + sum_3;
end

该函数分为三部分,分别是求sum_1、sum_2、sum_3,分析每一部分的复杂度再去最大的量级作为整个函数的复杂度。

在上面提到过,当N达到无限大的时候,一段代码的复杂度,是按照最大量级来取的,就是说只需要关注这个段代码中最复杂的部分,也就是 yield 3

yield 3的复杂度为O(n²)

所以得出结论

总的时间复杂度就等于量级最大的那段代码的时间复杂度

乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

简单来讲乘法法则就是嵌套循环,拿之前的一个例子来讲:

1
2
3
4
5
6
7
8
9
10
11
12
def cal(n)
sum = 0

for i in 0..n
j = 1
for j in 0..n
sum = sum + i*j
end
end

return sum
end

外层循环的复杂度是 n,内层循环的复杂度也是n,所以该函数的复杂度为 n*n

几种常见时间复杂度的实例分析

常见的复杂度量级如下,按数量级递增:

  • 常数级 O(1)
  • 对数级O(logn)
  • 线性级O(n)
  • 线性对数级O(nlogn)
  • 平方级O(n²) 立方级 O(n³)
  • 指数级O(2∧n)
  • 阶乘级O(n!)

对于刚罗列的复杂度量级,我们可以粗略地分为两类,多项式量级和非多项式量级。其中,非多项式量级只有两个:O(2n)O(n!)

O(1)

O(1) 只是常量级时间复杂度的一种表示方法,并不是指只执行了一行代码。比如这段代码,即便有 3 行,它的时间复杂度也是 O(1),而不是 O(3)

1
2
3
i = 1
j = 2
sum = i + j

只要代码的执行时间不随 n 的增大而增长,这样代码的时间复杂度我们都记作 O(1)。或者说,一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1)。

O(logn)、O(nlogn)

1
2
3
4
i = 1
while i < n do
i = i*2
end

第三行代码是执行最多次的,我们只需要计算该代码执行了多少次,就可以看出整段代码的复杂度:

2^k = n

所以我们只需要知道k的值 就可以知道整块代码的复杂度:

k = log₂n

即复杂度为O(log₂n)

同样的在采用大 O 标记复杂度的时候,可以忽略系数,即 O(Cf(n)) = O(f(n))

当N趋于无限大时,对数的大小可以忽略底数,在对数阶时间复杂度的表示方法里,我们忽略对数的“底”,统一表示为 O(logn)。

如果一段代码的时间复杂度是 O(logn),我们循环执行 n 遍,时间复杂度就是 O(nlogn) 了。而且,O(nlogn) 也是一种非常常见的算法时间复杂度。比如,归并排序、快速排序的时间复杂度都是 O(nlogn)。

O(m+n)、O(m*n)

代码的复杂度由两个数据的规模来决定

1
2
3
4
5
6
7
8
9
10
11
sum_1 = 0
p = 1
for p in 0..100
sum_1 = sum_1 + p
end

sum_2 = 0
q = 1
for q in 0..m
sum_2 = sum_2 + q
end

m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大,所以我们在表示复杂度的时候,就不能简单地利用加法法则,省略掉其中一个。所以,上面代码的时间复杂度就是 O(m+n)

空间复杂度分析

时间复杂度的全称是渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系。

类比一下,

空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系

常见的空间复杂度就是 O(1)、O(n)、O(n2 ),即程序运行和数据空间之间的关系

1
info = Array.new(n)

该代码的空间复杂度就是n


  • Post title:复杂度分析
  • Post author:Varsion
  • Create time:2020-07-28 11:23:12
  • Post link:https://blog.varsion.cn/post/a1a87ec3.html
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
Comments