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)
网友评论