数据结构和算法(二):复杂度分析

执行效率:运行的更快,更省空间

时间复杂度

  • 假设:每行代码执行的时间都一样,为unit_time
  • 分析原因:测试结果依赖测试环境和数据规模,所以不能事后分析,需要事前粗略估计。
  • 大O复杂度表示法:不具体表示代码真正的执行时间,只代表代码执行时间随数据规模增长的变化趋势,也叫渐进时间复杂度,简称时间复杂度。
  • 复杂度排序:O(1) < O(logn) < O(n) < O(nlogn) < O(n的平方)

分析方法

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

非多项式量级

指数和阶乘

多项式时间复杂度

1、 O(1)

表示常量级的时间复杂度,不是说只执行了一行代码。

一般情况下,只要不存在递归,循环,或者成千上万行代码,时间复杂度都是O(1)

2、 O(logn)、O(nlogn)

对数级时间复杂度,最难分析。
归并排序、快速排序的时间复杂度都是 O(nlogn)。
如下:

 i=1;
 while (i <= n)  {
   i = i * 2;
 }

3、 O(m+n)、O(m*n)

复杂度有两个数据的规模决定,但是无法评估m和n谁的量级大,故不能省略任何一个。
如下:

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

空间复杂度

  • 算法的存储空间和数据规模之间的增长关系。
  • 常见的空间复杂度:O(1),O(n),O(n的平方),对数阶的用得少。
    思考:

    Q&A

    Q: 讲到存储一个二进制数,输入规模(空间复杂度)是O(logn) bit?
    A: 比如8用二进制表示就是3个bit。16用二进制表示就是4个bit。以此类推 n用二进制表示就是logn个bit

你可能感兴趣的