数据结构和算法

数据结构和算法知识栈

▷ 复杂度分析

用数据结构和算法来解决问题，解决的好不好，效率高不高，省不省空间，这个用形容词是没法描述的，必须用定量的指标来分析，这就会用到贯穿整个数据结构和算法的“复杂度分析”。一般分为时间复杂度和空间复杂度。

大O复杂度表示法

假设每行代码语句执行的时间是一样的，不论有多少行代码，同一行代码执行多少次，那么，可以得到一个简单的规律，所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。总结成一个公式，即：T(n) = O(f(n))。
其中，T(n) 表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。这就是大O时间复杂度表示法。

时间复杂度

• 大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫做渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
• 当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：； 。
• 分析方法：
  1. 关注循环次数最多的代码
     大O复杂度表示法，只是表示一种变化趋势，忽略掉公式中的常量、低阶和系数，只需要记录一个最大阶的量级。记录下来循环次数最多的代码的量级，就是整段要分析代码的时间复杂度。
  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))).
• 复杂度量级：
  前5种为多项式量级，后两种为非多项式量级 和，当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。
  1. 常量阶： ;
     O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)
  2. 对数阶： ;
     对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。
     i=1;
while (i <= n) {
i = i * 2;
}
     如以上代码，每执行一次，i乘以2，最后执行次数就是,这段代码时间复杂度就是,而对数之间是可以互相转换的， 就等于 * ,其中 是一个常量,所以， 就等于 。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 。
  3. 线性阶： ;
     线性阶时间复杂度要灵活计算，如果两个规模不一样大小的循环，时间复杂度不能简单表示为其中一个，就会有加法或乘法，如、
  4. 线性对数阶： ;
     线性对数阶就是将对数阶循环了n次，如归并排序、快速排序的时间复杂度都是 。
  5. 平方阶： ; 立方阶： ; ……K次方阶： ；
  6. 指数阶： ;
  7. 阶乘阶： ;

空间复杂度

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
我们常见的空间复杂度就是 、、，像 、 这样的对数阶复杂度平时都用不到。空间复杂度分析比时间复杂度分析要简单很多。