复杂度分析

思考

给出纸和笔，要求需要画一个网格，包含16个格子，都有什么方法可以完成。

算法1：每次只能画一个格子，画一个格子是一次操作，画16个格子需要16次操作。

算法2：尝试将纸对折，这里对折即为一次操作。对折 1 次得到两个格子，对折两次，得到 4 个格子，不难得出，如果我们需要一个包含16格子的网格，只需将纸折叠 4 次就可实现。

算法1需要操作数为16次，算法2的操作数是4次。

什么是复杂度

算法的复杂度是衡量算法执行效率的一种度量方式，它描述了随着输入规模增加，算法所需执行的操作数或时间的增长情况。通常用时间复杂度和空间复杂度来衡量。

uml diagram

复杂度分析的意义

复杂度分析提供了一种客观的方式来比较不同算法之间的性能优劣。可以确定哪个算法在给定的输入规模下更高效。有助于选择最适合特定问题的算法，以提高程序的执行效率。

通过对算法的复杂度进行分析，可以确定算法中的性能瓶颈所在，并提供改进的方向。

在开发过程中，对算法的复杂度进行分析可以帮助开发者意识到可能出现的性能瓶颈，并在早期进行优化，避免在后期遇到严重的性能问题。

大O表示法

算法的渐进时间复杂度：T(n)=O(f(n))。

大O表示法是一种描述算法复杂度的数学符号标识方法，主要用来恒来算法的时间复杂度即执行时间的增长率，或者标识空间复杂度也就是存储空间的增长率。

大O表示法后边以O(f(n))来表示复杂度。

大O表示法表示的是复杂度的上界，即输入规模趋于无穷大时，时间和空间的增长速度。

大O表示法是一种抽象的表示方式，它忽略了常数因子和低阶项。因为当数据项无限大时，常数因子以及相比较的低阶项的影响均可忽略。

常见的时间复杂度

类型	时间复杂度（越来越大）	应用场景
常数阶	O(1)
对数阶	O(logN)	二分查找
线性阶	O(n)	简单查找
线性对数阶	O(nlogN)	快速排序
平方阶	O(n²)	选择排序

时间复杂度-O(1)

常数阶是指简单变量定义或者运算，复杂度不会随着任何变量的变化而变得更复杂，在这个过程中，时间复杂度都是常量级别，这种常量级别的情况，统一算作 O(1)。

即使变量定义多次，也按照O(1)统计。

// 即使是3行，也是O(1)
int i = 8;
int j = 6;
int sum = i + j;

在循环中，循环次数也是常数，所以也按照O(1)统计。

// 循环次数是一个常量，也是O(1)
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
  sum_1 = sum_1 + p;
}

时间复杂度-O(n)

-当算法的运行时间会随着 n 的增加而不断增加，即变量 n 会影响算法的复杂度时，将复杂度定义为O(n)。

// 总复杂度为O(n)
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

时间复杂度-O(n²)

嵌套循环。
如下代码每一次的外循环内循环都需要进行n次，所以总的时间复杂度为相乘的关系，标识为O(n^2^)。

// O(n²)
for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

时间复杂度-O(logn)

当设定条件为(i<n)的时候，其实际循环次数为log2N次。这种情况的时间复杂度，会统一认为为 O(logn) 。

// O(logn)
int i = 1;
while(i<n)
{
    i = i * 2;
}

时间复杂度-O(nlogn)

以下代码外层循环需要执行n次，内层需要logn次，根据嵌套的计算方式，总体复杂度用相乘来表示即O(nlogn)。

// O(nlogn) 
// 这段为 O(n)
for(m=1; m<n; m++)
{
    i = 1;
    //这段为 O(logn)
    while(i<n)
    {
        i = i * 2;
    }
}

多段代码取最大

以下代码中包含三块逻辑，三块逻辑的复杂度分别为：O(1)，O(n)，O(n^2^)。
此时假设 n 为无限大，那么低阶就可被忽略，最终的时间复杂度即为O(n^2^)。

// 总复杂度等于量级最大的那段代码的复杂度
int cal(int n) {
   int sum_1 = 0;
   int p = 1;
   // O(1)
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }

   int sum_2 = 0;
   int q = 1;
    // O(n)
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
  // O(n²)
   int sum_3 = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }

   return sum_1 + sum_2 + sum_3;
 }

多个规模求加法

代码的复杂度由两个数据的规模决定。
m 和 n 是表示两个数据规模。无法事先评估 m 和 n 谁的量级大。所以取加法。

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  // 复杂度为O(m)
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }
  int sum_2 = 0;
  int j = 1;
  // 复杂度为O(n)
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

嵌套代码求乘积

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

// O(m*n)
for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

总结-时间复杂度

时间复杂度	对应场景
O(1)	常量级
O(n)	单个循环，且过程没有变化。
O(logn)	单个循环，但是时间复杂度会降低。
O(m+n)	两个循环且无法确定两个复杂度谁大的情况
O(n²)/O(m*n)	嵌套循环
O(nlogn)	O(n) 与 O(logn) 嵌套

空间复杂度

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity）。
表示算法的存储空间与数据规模之间的增长关系。
同样可以使用大O表示法。

空间复杂度-O(1)

// 代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

空间复杂度-O(n)

// 这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)
// 此数组占用的空间为n
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}