执行效率：运行的更快，更省空间

工夫复杂度

  • 假如：每行代码执行的工夫都一样，为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