算法复杂度

时间复杂度

大O时间复杂度 , 并不具体表示代码真正执行的时间, 而是 表示代码执行时间随数据规模增长的变化趋势 , 也叫做渐进时间复杂度, 简称时间复杂度

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

几种常见的时间复杂度实例

• 非多项式量级只有两个：O(2n) 和 O(n!); 时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题; 当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

O(1)

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

O(logn)、O(nlogn)

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

说明: i的值是个等比数列，因此x即为代码执行的次数，

$$ x=log_2n $$

；又由于

$$ log_3n=log_32*log_2n $$

, 而

$$ log_32 $$

可忽略不计, 因此, 在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)

O(m+n)、O(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;
}

最好/最坏时间复杂度

平均时间复杂度

示例: 查找变量在数组中的位置, 简单计在数组中概率1/2, 不在数组中概率1/2, 在数组中出现在0到n-1位置的概率也一样都为1/n (因此变量在0~n-1中的概率为1/2n), 平均时间复杂度的计算过程如下:

(3n+1)/4, 用大 O 表示法来表示，去掉系数和常量，加权平均时间复杂度仍然是 O(n)

均摊时间复杂度

 //这段代码实现了一个往数组中插入数据的功能。
 //当数组满了之后，也就是代码中的 count == array.length 时，
 //我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。
 // 但如果数组一开始就有空闲空间，则直接将数据插入数组。
 
 // array表示一个长度为n的数组
 // 代码中的array.length就等于n
 int[] array = new int[n];
 int count = 0;
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

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

最好时间复杂度为O(1), 最快时间复杂度为O(n), 平均时间复杂度为O(1)

对于 insert() 函数, 一般都是一个 O(n) 插入之后，紧跟着 n-1 个 O(1) 的插入操作，循环往复。针对这种特殊的场景, 使用摊还分析法, 把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

---

空间复杂度

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系, 常见的空间复杂度就是 O(1)、O(n)、O(n2 )