了解算法复杂度

编程入门行业动态更新时间:2024-10-28 00:21:27

了解算法<a href=https://www.elefans.com/category/jswz/34/1767520.html style= 复杂度"/>

了解算法复杂度

概述

算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。应用于数学和计算机导论。一般编程中需要分析一段算法执行效率的时候会作为指标来用。

如何衡量算法的效率？通常是用资源，例如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)。