复杂度计算

简介

不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法

时间复杂度

时间复杂度代表代码执行时间随数据规模增长的变化趋势，所有代码的执行时间 T(n) 与每行代码的执行次数 f(n) 成正比，所以T(n) = O(f(n))

分析方法

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

几种常见时间复杂度实例分析

O(1)

一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)

O(logn)、O(nlogn)

如代码，i = i * 2执行后的结果为 2^k > n， 所以代码会执行k次，通过数学计算，k=log2n，通常情况下底数可以省略，所以复杂度为O(logn)

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

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

代码的复杂度由两个数据的规模来决定

空间复杂度

算法的存储空间与数据规模之间的增长关系