关于数据结构和算法:数据结构和算法二复杂度分析

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

工夫复杂度

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