1. 复杂度定义及常见量级
复杂度分为时间复杂度和空间复杂度.
以下面的函数为例:
- 1 int count(int n) {
- 2 int[] arr = new arr[n];
- 3 for(int i = 0; i <arr.length; i++) {
- 4 arr[i] = i;
- 5 }
- 6 return 0;
- }
我们先来确定这个函数运行到结束所用的时间. 因为环境不同, 运行一行代码所需要的时间也不同, 假设任何条件下, 一行代码的运行时间都为 U.
第二行的运行时间为 U. 第三行第四行都是循环, 每一次运行时间是 U, 运行了 n 次也就是 n*U. 第六行运行时间也是 U.
这段代码一共的运行时间是 U + nU + nU +U = (2n+2)*U = T(n). 根据这个计算公式, 当 n 是 2 时, 运行时间是 6U. 当 n 是 3 时, 运行时间是 8U.
如果 n 是一个确定值, 这个时间一定可以得出来, 但 n 是不确定的, 我们需要一个方法来表示当数据增长或者减少时, 代码执行的时间呈怎样的一个变化趋势. 当然, 我们刚刚得出的那个公式可以得出这个趋势, 但是在数据规模特别大的情况下, 除了最高阶的变量, 其它都会变得无足轻重. U 的大小更不需要关心, 因为我们求的是趋势而不是具体某一个点的时间.
这个执行时间随数据规模变化的趋势, 叫做时间复杂度, 一般用 O 表示. 比如上面的那个公式用 O 表示, 去掉系数, 常数, 低阶项, 就会变成 O(n).O(n) 表示这段代码的最终的时间复杂度.
确定了时间, 我们再来确定空间. 假设单位空间为 S. 上方代码只有第二行, 第三行涉及到了空间的申请. 第二行声明了一个数组占用空间为 n*V, 第三行声明了一个变量, 占用空间为 V, 该程序执行一共占用的空间是 (n + 1)V. 最后的算法与时间复杂度类似, 得出的空间复杂度为 O(n).
下面是常见的复杂度, 通过图片可以比较直观的看出来不同复杂度执行效率的差别.
O(1): 只要没有循环, 递归定义, 时间复杂度就是 O(1);
O(n): 一次循环
O(logn): 用于循环的值呈指数增长
O(nlogn): 正常循环嵌套指数增长的循环
O(n^2): 一次嵌套循环
常见复杂度
2. 常见的排序及分析
如果相同值的前后顺序在排序后不会改变, 则这个排序是稳定的. 如 A[i] = 5, A[j] = 5, 排序后第一个 5 还是在第二个 5 前面, 这个排序就是稳定的.
- Bubble Sort
- let arr = [0,2,3,3,5,1,1,7,2,9,10]; // 1
- for(let i = 0;i < arr.length -1;i++) {
- let flag = flase;
- for(let j = 0;j < arr.length -1 -i;j++) {
- if(arr[j]>arr[j+1]) {
- let temp = arr[j+1];
- arr[j+1] = arr[j];
- arr[j] = temp;
- flag = true;
- }
- }
- if(!flag)break;
- }
- Selection Sort
- for(let i = 0;i <arr.length - 1;i++) {
- let min = i;
- for(let j = i + 1;j < arr.length;j++) {
- if(arr[j] < arr[min]) min = j;
- }
- let temp = arr[i];
- arr[i] = arr[min];
- arr[min] = temp;
- }
- Insertion Sort
- for(let i = 1;i < arr.length;i++) {
- let key = arr[i];
- let j = i;
- for(j;j>0;j--) { // 此处也可以不用 break, 在循环体里 j>0&&key<arr[j-1]
- if(arr[j-1]>key) {
- arr[j] = arr[j-1];
- } else {
- break
- }
- }
- arr[j] = key;
- }
- partion-exchange Sort
- var quickSort = function(arr) {
- if (arr.length <= 1) { return arr; }
- var pivotIndex = Math.floor(arr.length / 2); // 基准位置 (理论上可任意选取)
- var pivot = arr.splice(pivotIndex, 1)[0]; // 基准数 此处获得基准数并将基准数从数组中去掉
- var left = [];
- var right = [];
- for (var i = 0; i <arr.length; i++){
- if (arr[i] < pivot) {
- left.push(arr[i]);
- } else {
- right.push(arr[i]);
- }
- }
- return quickSort(left).concat([pivot], quickSort(right)); // 链接左数组, 基准数构成的数组, 右数组
- }
- Merge Sort
- function merge(arr, p, q, r) {
- let leftArr = arr.slice(p, q + 1)
- let rightArr = arr.slice(q + 1, r + 1)
- leftArr.push(Number.POSITIVE_INFINITY)
- rightArr.push(Number.POSITIVE_INFINITY)
- let i = 0;
- let j = 0;
- for (let k = p; k <= r; k++) {
- if (leftArr[i] <= rightArr[j]) {
- arr[k] = leftArr[i]
- i++
- } else {
- arr[k] = rightArr[j]
- j++
- }
- }
- }
- function mergeSort(arr, p, r) {
- if (p>= r) return;
- let q = Math.floor((p + r) / 2)
- mergeSort(arr, p, q)
- mergeSort(arr, q + 1, r)
- merge(arr, p, q, r)
- }
- mergeSort(arr, 0, arr.length - 1)
来源: http://www.jianshu.com/p/3487cdf096e9