数据结构与算法

发表于 |

复杂度分析

为什么要进行复杂度分析

  • 和性能测试相比，有不依赖执行环境、成本低、效率高的特点
  • 掌握复杂度分析，将能编写出性能更高的代码，有利于降低系统开发和维护的成本

复杂度分析

  • 时间复杂度： 不具体表示代码的真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势
  • 空间复杂度： 代码所占空间随数据规模增长的变化趋势

时间复杂度分析

  • 加法法则(总复杂度等于量级最大的那段代码的复杂度)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    function sum(n) {
      var sum = 0;
      for(var i = 0; i <= n; i++) {
        sum = sum + i;
      }
      return sum;
    }
    // var sum = 0; 为常量级的执行时间与n的大小无关
    // for 循环 的两行代码需要执行n次，所以这个函数的时间复杂度为O(n)

  • 乘法法则(嵌套代码的复杂度等于嵌套内外代码的乘积)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    function cal(n) {
      var res = 0;
      for(var i = 0; i <= n; i++) {
        for(var j = 0; j <= n; j++) {
          res = res + i + j;
        }
      }
    }
    // O(n * n) = O(n2)

时间复杂度量级 从小到大

  • O(1)
  • O(logn)
  • O(n)
  • O(nlogn) 归并排序 快速排序
  • O(n^2), O(n^3)…
  • O(2^n) 非多项式
  • O(n!) 非多项式

当有多个参数变化时，加法原则就不适用了，但乘法还是适用

1
2
3
4
function cal(m, n) {
  return sum(m) + sum(n);
}
// 时间复杂度 O(m + n)

空间复杂度分析

时间复杂度会了，空间复杂度很简单

最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度、均摊时间复杂度

1
2
3
4
5
6
7
8
9
function find(array, x) {
  let pos = -1;
  for(let i = 0; i < array.length; ++i) {
    if (array[i] === x) {
      pos = i;
    }
  }
  return pos;
}

最好、最坏情况时间复杂度

这段代码是在array中查找x值。时间复杂度为O(n),如果查找到相等值就立即停止，那么时间复杂度就分两种情况
最好情况时间复杂度为O(1)， 最坏情况时间复杂度为O(n)
因为x在array中的位置有n+1种可能那么平均时间复杂度为（1+2+3…+n+n）/（n+1），用大O表示法就是O(n),但是这样计算是有些问题的。
因为x在数组里和不在数组里的概率都是1/2。所以x出现在0-n-1中任意位置的概率都为1/2n,所以(1+2+3+…n)*1/2n + n*1/2 = (3n + 1) / 4; 结果还是O(n)

均摊时间复杂度 方法：平摊分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const array = new Array(10);
const count = 0;
function insert(x) {
  if (count === array.length) {
    let sum = 0;
    for (let i = 0; i<array.length; i++) {
      sum += array[i];
    }
    array[0] = x;
    count = 0;
  }

  array[count] = val;
  ++count;
}

当array已满时，对array求和放在开头，然后再insert。
最好：O(1)
最坏：O(n)
平均：O(1)
均摊：O(1)，将1次的O(n)操作均摊到n - 1次的O(1)操作中
当对一个数据结构进行一组连续的操作时，大部分的情况下时间复杂度都很低，可以利用均摊分析法了。

数组

为什么数组序号从0开始

数组一个线性表结构。用一组连续的内存空间，来存储一组具有相同类型的数据。这就使得数组支持根据下标随机访问。
a[k].address = base.address + k type.size
a[k].address = base.address + (k - 1) type.size
相比之下，数组序号从1开始会多一次减法运算，再加上c语言采用这种方式，所以。。。

JVM 标记清除垃圾回收算法

将要释放清除的对象标记，之后再执行清除操作，缺点是会产生内存碎片的问题，很有可能导致下一次分配一块连续较大的内存空间，由于找不到合适的，又触发一次垃圾回收操作。

链表

约瑟夫问题 可以用循环链表实现

1
2
3
4
5
6
7
function f(n, m) {
  let s = 0;
  for (let i = 2; i <= n; i++) {
    s = (s + m) % i;
  }
  return s;
}

链表练习题：

  • 单链表反转
  • 链表中环的检测
  • 两个有序的链表合并
  • 删除链表倒数的第n个节点
  • 求链表的中间节点