数据结构和算法

数据结构和算法

数据结构是为算法服务的，算法要作用在特定的数据结构。

10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树；

10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

时间复杂度和空间复杂度分析

数据结构和算法本身就是为了解决“快”和“省”的问题。让代码运行更快，更省储存空间。那首先我们就要先了解自己写的代码复杂度，这里就需要用到时间复杂度和空间复杂度分析。

时间复杂度

表示代码执行时间随数据规模增长的变化趋势

空间复杂度

表示算法的存储空间与数据规模之间的增长关系

大O复杂度表示法：

分析技巧：

1、只关注执行次数最多的一段代码2、加法规则：量级最大代码的复杂度3、乘法规则：嵌套代码的复杂度等于内外复杂度的乘积

T(n)代码执行时间，O(f(n))表示代码执行次数

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

常用的复杂度级别

多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长，包括，O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n^2)(平方阶)、O(n^3)(立方阶)。

非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这列算法性能极差。包括，O(2^n)(指数阶)、O(n!)(阶乘阶)

复杂度分析的四个概念

• 最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度。
• 最好情况时间复杂度：代码在最理想情况下执行的时间复杂度。
• 平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。
• 均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。