当前位置： 首页 >> 数据结构与算法 >> 定义与复杂度

---

定义与复杂度

2020-07-04 17:55:45 星期六  阅读：2685

---

参考文章：[极客时间《数据结构与算法之美》专栏](https://time.geekbang.org/column/intro/100017301?utm_campaign=guanwang&utm_source=baidu-ad&utm_medium=ppzq-pc&utm_content=title&utm_term=baidu-ad-ppzq-title "极客时间《数据结构与算法之美》专栏") ####定义 数据结构是为算法服务的，算法要作用在特定的数据结构之上。 **`数据结构就是指一组数据的存储结构`** **`算法就是操作数据的一组方法`** 数据结构的重要概念：复杂度分析，包括空间复杂度和时间复杂度。其中时间复杂度又分为最好、最坏、平均、均摊时间复杂度。 复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。 ####20个最常用的数据结构与算法 | 算法 | 数据结构 | | ------------ | ------------ | |递归 |数组| |排序 |链表| |二分查找 |栈| |搜索 |队列| |哈希算法 |二叉树| |贪心算法 |堆| |分治算法 |跳表| |回溯算法 |图| |动态规划 |Trie| |字符串匹配算法 |树| ####复杂度分析 传统的分析代码执行效率分析，都需要把代码跑一遍，通过统计、监控等手段来得到执行时间等性能指标。这种叫做事后统计法。这种统计的劣势如下： - 测试效果非常依赖测试环境； 测试结果受到数据规模的影响很大； **`时间复杂度`** `时间复杂度表示算法的执行时间与数据规模之间的增长关系`。也就是你写的代码，随着数据量的增长，执行效率是指数级增长还是缓慢增长； 所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估算执行效率的方法；因此，我们就引出了大O表示法。如何用此种方法分析一段代码的时间复杂度？可通过下面三个实用的方法 - 只关注循环执行次数最多的一段代码； - 加法法则：总复杂度等于量级最大的那段代码的复杂度； 乘法法则：嵌套代码的复杂度等于嵌套内外代码的复杂度乘积 几种常见的多项式时间复杂度 ``` O(1) O(logn)、O(nlogn) O(m + n) 、O(m * n) ``` **`空间复杂度`** 空间复杂度表示算法的存储空间与数据规模之间的增长关系。 比如，下面的代码，只有第一个for循环里占用内存（存储空间） ``` void print(int n){ int i = 0; int [] a = new int[n]; for (i; i < n; i++){ a[i] = i * i; } for (i = n -1; i > 0; --i){ print out a[i] } } ``` 常见的空间复杂度 ``` O(1) O(n) O(n^2) O(nlogn) O(logn) ``` ####复杂度的种类 - 最好情况时间复杂度 最坏情况时间复杂度 平均情况时间复杂度（也叫加权平均时间复杂度） - - 最好和最坏时间复杂度对应的都是极端情况，发生的概率不大。 - 均摊时间复杂度（其实就是一种特殊的平均时间复杂度）