时/空间复杂度

时间复杂度：

含义：若存在函数 f(n)，使得当 n 趋近于无穷大时，T(n)/ f(n)）的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作 T(n)= O(f(n))，称 O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

• 通过观察一个方法在执行不同的输入情况时，所呈现的结果，并以线段表示趋势而得到线性时间复杂度
• 简单理解：一个算法或是一个程序在运行时，所消耗的时间（或者代码被执行的总次数）
• 大 O 表示法：T(n) = O(f(n))，算法的时间复杂度通常用大 O 来表示，其中 T 表示时间，称为 O(f(n))为算法的渐进时间复杂度
• 时间复杂度的数量级，其原则是：
  • 省略常数，如果运行时间是常数量级，用常数 1 表示
  • 保留最高阶的项
  • 变最高阶项的系数为 1
  • 示例：2n³ + 3n² +7 变成 O(n³)

时间复杂度的阶

• 常数阶: O(1)

  • 看代码： 每次调用方法时，里面的语句执行的次数(如有循环，次数多)，其它语句只执行一次所以为 O(1)
  • 示例：

    // 不管n为多少，只执行一遍
    function sumUp(n) {
    	return (n / 2) * (1 + n) 
    }

• 对数阶: O(logⁿ)

  • i 的值随 n 成对数增长，即为 log₂ ⁿ,时间复杂度 T(n) = O(logⁿ)
  • 示例：

    // n = 32 则 i=1,2,4,8,16,32
    for (let i = 1; i <= n; i = i * 2) {
    	console.log('对数阶：' + n)
    }

• 线性阶: O(n)

  • y = f(x),即 T(n) = O(n)
  • 示例：

    for (let i = 1; i < n; i++) {
    	console.log(n)
    }

• 线性对数阶:O(nlogⁿ)

  • 归并排序的复杂度就是这样，将对数阶的代码循环 n 遍，即两层循环,但内层循环是外层循环的次数于外层循环形成对数阶。
  • 示例：

    for (let m = 1; m <= n; m++) {
    	let i = 1
    	while (i < n) {
    		i = i * 2
    		console.log(i)
    	}
    }

• 平方阶: O(n²)

  • 也是两层循环
  • 示例：

    for (let i = 1; i <= n; i++) {
    	for (let j = 1; j <= n; j++) {
    		console.log(n)
    	}
    }

• 总结：

  • 当 x 轴 n 的值越来越大时，y 轴耗时的时长为：O(1) < O(logⁿ) < O(n) < O(nlogⁿ) < O(n²)

空间复杂度

一般指额外空间复杂度。看的是定义的变量，输入数组不算额外空间，输出空间不算额外空间。 使用的额外空间与数据量没有关系就称为 O(1),表示使用常数量级别的额外空间

• 表示的是算法的存储空间和数据之间的关系，即一个算法在运行时，所消耗的空间
• 所有值都存储在内存中，而这些值在内存的占用情况，内存泄漏与空间复杂度无关
• 创建一个变量存储值，在每次循环迭代的过程中，这个值会改变，每次改变都是新值，并且随着迭代变大变小。 画线看图的整体趋势得出结果

  算法	空间复杂度	原因
  循环	O(1)	操作一个或相同的数，没有‘永久’新值产生的迭代
  递归	O(n)	为每个嵌套函数调用创建一个新值(接收的参数)
  线性搜索	O(1)	迭代期间没有产生‘永久’新值
  二分查找	O(1)	迭代期间产生‘永久’的新值
  冒泡搜索	O(1)	迭代期间产生‘永久’的新值
  快速排序	O(n)	嵌套函数调用将创建新值
  归并排序	O(n)	嵌套函数调用将创建新值

空间复杂度的阶

• 常数阶 O(1): int i;
• 线性阶 O(n): int [] arr;
• 平方阶 O(n²): int [][] arr;