复杂度"/>
了解算法复杂度
概述
算法复杂度是指算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源。应用于数学和计算机导论。一般编程中需要分析一段算法执行效率的时候会作为指标来用。
如何衡量算法的效率?通常是用资源,例如CPU(时间)占用、内存占用、硬盘占用和网络占用。一种常用的衡量复杂度的效率的方法 大O表示法(O为order的首字母的大写) 考虑的是CPU(时间)占用。
下面是分析算法时常用一下几类函数:
- O(1) 常数
- O(logN) 对数
- O(nlogN) 线性对数
- O(n) 线性
- O(n^2) 二次
- O(n^c) 多项式
- O(c^n) 指数
常数O(1)
function increment(num){return ++num;
}
假设运行increment(1)函数,执行事件为X。如果再用不同的参数(例如10)运行一次increment函数,执行事件依然是X。和参数无关,increment函数的性能都一样。因此,我们说上述函数的复杂度是O(1)。
对数O(logN)
function multiplication(num){var i = 1;while(i < num){i = i * 2;}return i;
}
从上面可以看出,在while循环里面,每次都讲i乘以2,乘完之后,i离num越来越近。我们试着求解一下,假设循环次之后i就大于num了,那这个循环就退出了,也就是2^n = num,n = log2^num ,即当循环log2^num次后运行结束。因此时间复杂度为O(logN)。
线性对数O(nlogN)
线性对数复杂度就是讲复杂度为O(logN)的函数执行n次的复杂度。
线性O(n)
function cycle(num){var j = 1;for(var i=0; i<num; i++){j++;}return j;
}
从函数逻辑可以看出,传入num为1,则for循环执行1次,num为2,执行2次,num为10,执行10次,num为n,执行n次。因此复杂度为O(n).
二次O(n^2)
以冒泡排序为例:
function bubbleSort(array){var length = array.length;var cost = 0;for(var i=0; i<length; i++){cost++;for(var j=0; j<length - 1; j++){cost++; if(array[j]>array[j+1]){swap(array, i, j+1); }}}console.log('cost for bubbleSort with input size '+ length +' is '+ cost);
}function swap(array, index1, index2){var aux = array[index1];array[index1] = array[index2];array[index2] = aux
}
传入大小为10的数组,执行开销是10(10-1)+10,即10^2 ,传入大小为100的数组,执行开销是100(100-1)+100,即100^2 。则复杂度为O(n^2)。
多项式O(n^c)
参考复杂度O(n^2)去理解,幂不是2,而是一个动态值。
指数O(c^n)
参考复杂度O(n^2)去理解,基数和幂是一个动态值。
参考资料
- 《学习JavaScript数据结构与算法》第十二章 算法复杂度
- 算法的时间与空间复杂度(一看就懂)
- 算法复杂度
- 算法中的大O表示法
- 算法概念:大O表示法/小o表示法/Ω/Θ
更多推荐
了解算法复杂度
发布评论