一 复杂度

复杂度是衡量代码运行效率的重要的度量因素。一段代码消耗的资源是什么。一般而言，代码执行过程中会消耗计算时间和计算空间，那需要衡量的就是时间复杂度和空间复杂度。

1.1 空间复杂度

空间复杂度，即算法运行的过程中所消耗的内存空间。java程序员一般不是很关心，因为我们的机器的内存很不用太关心。但是嵌入式开发还是比较注重的，毕竟有些硬件内存只有几兆的，甚至几十kb的。

1.2 时间复杂度

复杂度是一个关于输入数据量 n 的函数。假设你的代码复杂度是 f(n)，那么就用个大写字母 O 和括号，把 f(n) 括起来就可以了，即 O(f(n))。例如，O(n) 表示的是，复杂度与计算实例的个数 n 线性相关；O(logn) 表示的是，复杂度与计算实例的个数 n 对数相关。

1.2.1 时间复杂度计算原则

  1. 复杂度与具体的常系数无关，例如 O(n) 和 O(2n) 表示的是同样的复杂度。我们详细分析下，O(2n) 等于 O(n+n)，也等于 O(n) + O(n)。也就是说，一段 O(n) 复杂度的代码只是先后执行两遍 O(n)，其复杂度是一致的。
  2. 其次，多项式级的复杂度相加的时候，选择高者作为结果，例如 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。具体分析一下就是，O(n²)+O(n) = O(n²+n)。随着 n 越来越大，二阶多项式的变化率是要比一阶多项式更大的。因此，只需要通过更大变化率的二阶多项式来表征复杂度就可以了。

  3. O(1) 也是表示一个特殊复杂度，含义为某个任务通过有限可数的资源即可完成。此处有限可数的具体意义是，与输入数据量 n 无关。

    1.2.2 常见的时间复杂度

  4. 一个顺序结构的代码，时间复杂度是 O(1)

  5. 二分查找，或者更通用地说是采用分而治之的二分策略，时间复杂度都是 O(logn)
  6. 一个简单的 for 循环，时间复杂度是 O(n)
  7. 两个顺序执行的 for 循环，时间复杂度是 O(n)+O(n)=O(2n)，其实也是 O(n)

  8. 两个嵌套的 for 循环，时间复杂度是 O(n²）

    1.3 空间换时间

    我们都知道时间昂贵、空间廉价。因此我们优化的终极目标是：要采用尽可能低的时间复杂度和空间复杂度，去完成一段代码的开发。所以它的一般步骤是：

  9. 暴力解法。在没有任何时间、空间约束下，完成代码任务的开发

  10. 无效操作处理。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度
  11. 时空转换。设计合理数据结构，完成时间复杂度向空间复杂度的转移

    二 数据结构

    数据结构就是把数据元素按照一定的关系组织起来的集合，用来组织和存储数据。

    2.1 逻辑结构

    逻辑结构是从具体问题中抽象出来的模型，是抽象意义上的结构，按照对象中数据元素之间的相互关系分类。

    2.1.1 集合结构

    集合结构中数据元素除了属于同一个集合外，他们之间没有任何其他的关系
    image.png

    2.1.2 线性结构

    线性结构中的数据元素之间存在一对一的关系
    image.png

    2.1.3 树形结构

    树形结构中的数据元素之间存在一对多的层次关系
    image.png

    2.1.4 图形结构

    图形结构的数据元素是多对多的关系
    image.png

    2.2 物理结构

    逻辑结构在计算机中真正的表示方式（又称为映像）称为物理结构，也可以叫做存储结构。

    2.2.1 顺序存储结构

    把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的 ，比如我们常用的数组就是顺序存储结构。
    image.png
    PS: 适合查询，不适合插入

    2.2.2 链式存储结构

    把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的也可以是不连续的。此时，数据元素之间并不能反映元素间的逻辑关系，因此在链式存储结构中引进了一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。
    image.png
    PS:适合插入，不适合查询