Payne的个人小屋

Every day

0%

算法-复杂度分析

发表于 更新于 分类于 Valine：
本文字数： 1.5k 阅读时长 ≈ 1 分钟

算法其核心主要思考的是快和省的问题，而算法复杂度可细分为时间复杂度和空间复杂度
。时间复杂度是指执行所需要的工作量，空间复杂度是指执行所需要的内存空间。

时间复杂度

Big O Notation

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

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

这就是大 O 时间复杂度表示法。

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

image-20211224220519869

常见时间复杂度

从小到大

T(n)desc
$$O(1)$$Constant Complexity（常数复杂度）
$$O（log n）$$Logarithmic Complexity（对数复杂度）
$$O（n）$$Linear Complexity（线性复杂度）
$$O（n ^ 2）$$N Square Complexity（平方复杂度）
$$O（n ^ 3）$$N cubic Complexity（立方复杂度）
$$O（2 ^ n）$$Exponential Growth(指数)
$$O（n!）$$Factorial (阶乘)

并列相加，嵌套相乘

每次折半log N,递归一般为指数

image-20211224223240782

时间复杂度分析

  1. 只关注循环执行次数最多代码块
  2. 加法原则：总复杂度等于量级最大的代码块的复杂度
  3. 乘法原则：嵌套代码的复杂度等于嵌套内外代码块复杂度的乘积

Example

O(1)O(1)

1
2
3
4
# Python
x = 1
y = 2
z = x + y

O(logn)O(log _ n)

1
2
3
4
i = 1
while (i <= 100):
    i *= 2
    print(i)

O(n+m)O(n + m)

1
2
3
4
5
6
7
8
9
# Python
x = 1
y = 2

while (x <= 100):
    x += 1

while (x <= 1000):
    y += 1

O(m∗n)O(m * n)

1
2
3
4
5
6
7
8
9
10
11
12
13
# Python

for x in range(1, 10):
    for y in range(1, x + 1):
        print(f"{y} ^ {x} = {x * y}", end="\t")
    print('')

print("-------")

for x in range(9, 0, -1):
    for y in range(1, x + 1):
        print(f"{y} ^ {x} = {x * y}", end="\t")
    print('')

tip: x 为长， y 为高

最好、最坏、平均复杂度

1
2
3
4
5
6
7
8
def find_Girl(girl: list[int], number: int) -> int:
    i, pos, n = 0, -1, len(girl)
    while i < n:
        if girl[i] == number:
            pos = i
            break
        i += 1
    return pos

最好情况时间复杂度（best case time complexity）：最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度

最坏情况时间复杂度（worst case time complexity）：最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度

平均情况时间复杂度（average case time complexity）：

最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率其实都并不大。为了更好地表示平均情况下的复杂度,
使用平均情况时间复杂度
平均复杂度，顾名思义就是出现情况的概率，这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

均摊时间复杂度

均摊时间复杂度（amortized time complexity）：

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。尽管很多数据结构和算法书籍都花了很大力气来区分平均时间复杂度和均摊时间复杂度，均摊时间复杂度就是一种特殊的
平均时间复杂度

空间复杂度

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

数组

空间复杂度(Space Complexity) 是对一个算法在运行过程中新开辟存储空间大小的量度.

记做

s(n)=O(f(n))s(n) = O(f(n))

递归

不做任何优化，一般为指数阶。

bigocheatsheet