算法复杂度

2021-03-04 2022-04-24 Development > Coding > Thought 阅读次数：字数： 1.3k 时长 ≈ 1 分钟

算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括：时间资源和内存资源。

参考：

前言

算法的时间复杂度是在学习 python 的 deque 双端队列了解到的，所以文本主要是了解学习算法中的时间复杂度和空间复杂度。

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。

衡量算法的优劣，主要通过时间和空间两个维度衡量。

在计算机科学中，算法的 时间复杂度（Time complexity） 是一个函数，定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用 大 O 符号 表示，不包括这个函数的低阶项和首项系数。

在编程的过程中，不同的数据代表着不同的作用，并且执行的效率也不同。

大 O 符号，又被称为渐进符号，用于描述函数渐进行为的数学符号。更确切地说，是用另一个函数来描述一个函数常量级的渐进上界。使用这种方式时，时间复杂度可被称为渐进的，亦即考察输入值大小趋近无穷时的情况。

下图为常见的时间复杂度关系：

是用来度量算法的运行时间，记作 T(n)=O(f(n))。表示随着输入 n 的增大，算法所需要执行的时间的增长速度可以用 f(n) 来表示，

名称	运行时间 (T(n))	运行时间举例	算法举例
常数时间	O(1)	10	判断一个二进制数的奇偶
反阿克曼时间	O(α(n))		并查集的单个操作的平均时间
迭代对数时间	O(log*n)		分布式圆环着色问题
对数对数时间	O(log log n)		有界优先队列的单个操作
常数时间	O(1)	10	判断一个二进制数的奇偶
常数时间	O(1)	10	判断一个二进制数的奇偶
常数时间	O(1)	10	判断一个二进制数的奇偶
常数时间	O(1)	10	判断一个二进制数的奇偶
常数时间	O(1)	10	判断一个二进制数的奇偶
常数时间	O(1)	10	判断一个二进制数的奇偶

线性对数阶，将时间复杂度为 O(logn) 的代码循环 N 遍的时间复杂度就是 n * O(logN)，也就是 O(nlogN)

for ((m=1; m<n; m++)); do
  i=1
  while (( i< n )); do
    let i=i*2
  done
done

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

平方阶将 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)

for ((x=1; i<n; x++)); do
  for ((i=1; i<n; i++)); do
    j=1
    let j++
  done
done

x = 1
while i < n:
    i = 1
    while i < n:
        j = 1
        j += 1
    x += 1

空间复杂度（Space Complexity）是对一个算法在运行中临时占用存储空间的一个度量，同时反映的是一个趋势。用 S(n) 来定义。

常见的空间复杂度有： O(1) O(n) O(n²)