大O表示法

大O表示法全称大 O 时间复杂度表示法，表示代码执行时间随数据规模增长的变化趋势。大O表示法用于粗略地估计算法的执行效率，所以大O表示法只关注量级最大的那段代码（一般就是循环执行次数最多的那段代码）

时间复杂度

代码中不存在循环语句、递归语句，即时千行万行，复杂度也是 O(1)

代码中存在循环语句、递归语句

const print = n => {
  for (let i = 0; i< n; i++) {
    console.log(i)
  }
}

该方法中， print 方法中 for 循环执行了 n 次，所以时间复杂度是 O(n)

循环退出条件不是线性增加的

const print = n => {
 let i = 1
 while (i <= n)  {
   i = i * 2
   console.log(i)
 }
}

代码中循环条件变量 i 每循环一次就乘以 2 ，当 i 大于 2 时循环结束。因此循环次数为

2^0 * 2^1 * 2^2 * 2^3 * .... 2^x = n

因此x = log2n ，大O简写为 O(logn)

如果代码中有两个循环，分别循环了 m 次和 n 次。如果这两个循环存在嵌套关系，则其复杂度为 O(m*n) ，如果不存在嵌套关系，则其复杂度为 O(m+n)

空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1) 举例：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

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

空间复杂度 O(n)

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

最后更新于4年前