数据结构与算法小结01-复杂度01

数据结构

• 线性结构：数组、链表，栈、队列、哈希表
• 树：二叉树、二叉堆
• 图等复杂数据结构

时间复杂度

• 表示代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度，简称时间复杂度
• 对一个算法运行时间的度量。
• 所有代码的执行时间T(n) 与 每行代码的执行次数f(n) 成正比。
• 常见的时间复杂的从低到高的顺序，包含：O(1),O(logn)、O(n)、O(nlogn)、O(n^2)

大O时间复杂度表示法

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

• T(n) 表示 代码执行的时间
• n 表示数据规模的大小
• f(n) 表示每行代码执行的次数总和，因为是一个公式，所以用 f(n) 来表示。
• O 表示代码的执行时间 T(n) 与 f(n) 表达式 成正比关系。
• 当n很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。

时间复杂度分析方式

1. 只关注循环执行次数最多的一段代码:分析一个算法、一段代码的时间复杂度时，只关注循环执行次数最多的一段即可。
2. 加法法则：总的时间复杂度等于量级最大的那段代码的时间复杂度。 若 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。若 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))

复杂度量级

• 常量阶 O(1)
• 对数阶 O(logn)
• 线性阶 O(n)
• 线性对数阶 O(nlogn)
• 平方阶 O(n^2)、立方阶 O(n^3) … K次方阶 O(n^n)
• 指数阶 O(2^n)
• 阶乘阶 O(n!)

大致可分类两类：多项式量级 和 非多项式量级。

非多项式量级只有两个：O(2^n) 和 O(n!)

时间复杂度为非多项式的算法问题叫做 NP（Non-Deterministic Polynomial，非确定多项式） 问题。

当数据规模 n 越来越大时，非多项式量级算法的执行时间回急剧增加，求解问题的执行时间会无线增长。所以非多项式时间复杂度的算法是非常低效的算法。

常见的多项式时间复杂度

O(1)

一般情况下，只要算法中不存在循环、递归语句(意味着代码的执行时间不随 n 的增大而增长)，即使有上万行代码，其时间复杂度也是O(1)。

O(logn)、O(nlogn)

所有对数阶的时间复杂度都可以记为 O(logn)，原因是：

• 对数之间是可以相互转换的， 通过换底公式可得 log~3~n = log~3~2 * log~2~n
• 所以 O(log~3~n) = O(C * log~2~n)，C = log~3~2
• 根据大O时间复杂度表示法，系数可以忽略，故 O(log~3~n) = O(log~2~n)
• 因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。
• 如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了
• 归并排序、快速排序的时间复杂度都是 O(nlogn)

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

• m 和 n 是表示两个数据规模，比如一段段代码中两个并列循环。无法评估谁的量级更大，所以不能通过加法原则简单省略其中一个，所以此时代码的时间复杂度是 O(m+n) 。
• 加法规则需要改为：T1(m) + T2(n) = O(f(m) + g(n))
• 乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(n))

空间复杂度

• 对一个算法运行过程中临时占用存储空间大小的度量
• 表示算法的存储空间与数据规模直接的增长关系，全称渐进空间复杂度。
• 从低到高的顺序：O(1)、O(n)、O(n^2)等。
• O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到
• 递归的空间复杂度和递归深度成正比。

参考资料

数据结构与算法之美