数据结构和算法本身解决的是”快“和”省“的问题

时间复杂度、空间复杂度

代码执行时，所有代码的执行时间T(n)与每行代码的执行次数成正比
image.png

T(n)表示代码的执行时间，n表示数据规模的大小，f(n)表示每行代码执行的次数总和
大O时间复杂度表示法。大O时间复杂度实际并不具体表示代码真正执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫做渐进时间复杂度简称时间复杂度
**

时间复杂度分析

表示算法的执行时间与数据规模之间的增长关系

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

分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。
也就是说：总的时间复杂度等于量级最大的那段代码的时间复杂度
常见的时间复杂度
image.png
可以粗略的分为两类，多项式量级和非多项式量级。其中非多项式量级只有两个：指数阶和阶乘阶
多项式量级

  1. O(1)
    1. 只要算法中不存在循环语句、递归语句，即使有成千上万行代码，其时间复杂度也是O(1)
  2. O(logn)、O(nlogn)

空间复杂度分析

即渐进空间复杂度。表示算法的存储空间与数据规模之间的增长关系

常见的复杂度不多，如下
image.png

最好最坏时间复杂度

同一段代码在不同的情况下复杂度会出现量级差异。

  • 最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度
  • 最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度
  • 平均情况时间复杂度
  • 均摊时间复杂度：是一种特殊的平均时间复杂度？

思考

分析如下add()函数的时间复杂度

  2. // 全局变量，大小为10的数组array，长度len，下标i。
  3. int array[] = new int[10]; 
  4. int len = 10;
  5. int i = 0;
  7. // 往数组中添加一个元素
  8. void add(int element) {
  9.    if (i >= len) { // 数组空间不够了
  10.      // 重新申请一个2倍大小的数组空间
  11.      int new_array[] = new int[len*2];
  12.      // 把原来array数组中的数据依次copy到new_array
  13.      for (int j = 0; j < len; ++j) {
  14.        new_array[j] = array[j];
  15.      }
  16.      // new_array复制给array，array现在大小就是2倍len了
  17.      array = new_array;
  18.      len = 2 * len;
  19.    }
  20.    // 将element放到下标为i的位置，下标i加一
  21.    array[i] = element;
  22.    ++i;
  23. }

最好O(1)最坏O(n)