一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得T(n)/f(n)的极限值(当n趋近于无穷大时)为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度,简称时间复杂度(Time Complexity)。
计算方法:
- 选取相对增长最高的项
- 忽略所有低次幂项和最高次幂的系数
- 若是常数的话用O(1)
常见时间复杂度:
执行次数函数 | 时间复杂度 | 阶 |
---|---|---|
12 | O(1) | 常数阶 |
2n+3 | O(n) | 线性阶 |
2$$n^2$$+3n+1 | O( |
平方阶 |
5$$log_2{n}$$ + 20 | O(logn) | 对数阶 |
2n + 3n$$log_2{n}$$ +19 | O(nlogn) | nlogn阶 |
4$$n^3$$ + 2$$n^2$$+3n+1 | O( |
立方阶 |
O( |
指数阶 |
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。一般情况下,一个程序在机器上执行时,除了需要寄存本身所用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的辅助存储空间。
计算方法:
- 忽略常数,用O(1)表示
- 递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间
- 对于单线程来说,递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的空间的个数,因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。