- 广义上讲，数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。
- 数据在内存中是呈线性排列的，但是我们也可以使用指针等道具，构造出类似“树形”的复杂结构。
数据结构和算法.png
- 时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。空间复杂度全称是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
复杂度量级
- 如果一段代码的时间复杂度是 O(logn) ，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 。
- 多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2 n )和O(n!)。
- 常见的空间复杂度就是O(1)、O(n)、O(n 2 )，像O(logn)、O(nlogn)这样的对数阶复杂度平时都用不到。
时间复杂度
- 最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。
- 最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。
- 最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率其实并不大。为了更好地表示平均情况下的复杂度，我们需要引入另一个概念：平均情况时间复杂度。
- 平均情况时间复杂度就是，把每种情况发生的概率也考虑进去。全称应该叫加权平均时间复杂度或者期望时间复杂度。
- 只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。
对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。
平均和平摊基本就是一个概念，平摊是特殊的平均。在分析时间复杂度是 O(1) 还是 O(n) 的时候最简单就是凭感觉，出现 O(1) 的次数远大于出现 O(n) 出现的次数，那么平均平摊时间复杂度就是 O(1)
网友评论