大O表示法

[qingfengmy]

5月13日，一个自称面试官的在掘金上发了一篇文章《面试官：阮一峰版的快速排序完全是错的》，同日，阮一峰的博客被攻击，他在微博上称“这件事让我了解，有人真的恨我，即使我没有伤害任何人的利益。 ​​​”

---

1. 大O大法

大O大法是表示时间和空间复杂度的，时间指CPU的时间，空间指内存空间。

2. O(1)复杂度

function increase(n) {
	n++;
}

const a = new Date().getMilliseconds();// 取的毫秒值，如同getHour()
increase(1);
const b = new Date().getMilliseconds();
console.log(a, b, b - a);// 401 401 0

const a1 = Date.now();// 取毫秒值，1970年以来的毫秒值
increase(1000000000);
const b1 = Date.now();
console.log(a1, b1, b1 - a1);//1526296053404 1526296053404 0

问题，执行时间不到1毫秒，怎么办？

console.time(1);
increase(1);
console.timeEnd(1);//1: 0.112ms

console.time(2);
increase(1000000000);
console.timeEnd(2);// 2: 0.007ms

这种执行时间不会随着参数值增加而增加的，就是 常数阶。时间随着参数增加呈一条直线。

3. O(㏒n)复杂度

就是指它的时间随着参数值得增加呈Log函数状，开始曲线陡，后续曲线越来越平。

典型的算法是 二分法查找。

function binarySearch(target, arr) {
	let start = 0;
	let end = arr.length - 1;
	let i = 0;
	while (start <= end && i < 13) {
		let mid = Math.ceil(start + (end - start) / 2);
		if (arr[mid] == target) {
			return mid;
		} else if (arr[mid] > target) {
			end = mid;
		} else if (arr[mid] < target) {
			start = mid;
		}
		i++;
	}
	return -1;
}

for (var i = 1; i <= 100; i++) {
	console.time(i);
	binarySearch(9, new Array(100000 * i).fill(0).map((item, index) => index));
	console.timeEnd(i);
}

上面打了100条数据，这个log的曲线也很难出现。记住半分法的查找是log就行了。

4. O(n)复杂度

一次线性函数，是一条斜线。
典型的算法是顺序查找

function sortSearch(target, arr) {
	let i = 0;
	while (i < arr.length) {
		if (arr[i] == target) {
			return i;
		}
		i++;
	}
	return -1;
}

for (var i = 1; i <= 20; i++) {
	console.time(i);
	sortSearch(9, new Array(100000 * i).fill(0).map((item, index) => index));
	console.timeEnd(i);
}

5. O(n²)复杂度

/**
 * 冒泡排序: o(n^2) 每次循环把最大的沉底
 */
function bubbleSort(arr) {
	let len = arr.length;
	for (let i = 0; i < len; i++) {
		for (let j = 0; j < len - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				let temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	return arr;
}

// 生成随机整数
function random(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
}

// 生成len长度的随机数组
function generateArr(len) {
	let arr = [];
	for (var i = 0; i < len; i++) {
		arr.push(random(1, len));
	}
	return arr;
}

const arr = generateArr(5); // count 是10次
console.log(arr);
const result = bubbleSort(arr);
console.log(result);

const arr1 = generateArr(50);// count是1225次，乘10变成乘100，10的2次方
console.log(arr1);
const result1 = bubbleSort(arr1);
console.log(result1);

6. O(NlogN)

线性对数曲线，典型算法是 归并排序

/**
 * 归并排序
 * 快速排序是分数组，归并排序是合数组
 */
function merge(left, right) {
	// left和right的长度最多差1
	let temp = [];
	while (left.length && right.length) {
		if (left[0] < right[0]) {
			temp.push(left.shift());
		} else {
			temp.push(right.shift());
		}
	}
	// 到这里，left和right肯定有一个已经是空，temp只需要concat其中一个有效的就行
	return temp.concat(left, right);
}

function mergeSort(arr) {
	if (arr.length <= 1) {
		return arr;
	}
	let mid = Math.ceil(arr.length / 2);
	let left = arr.slice(0, mid);
	let right = arr.slice(mid);
	// 递归出口是arr.length<=1
	return merge(mergeSort(left), mergeSort(right));
}

// 生成随机整数
function random(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
}

// 生成len长度的随机数组
function generateArr(len) {
	let arr = [];
	for (var i = 0; i < len; i++) {
		arr.push(random(1, len));
	}
	return arr;
}

const arr = generateArr(10);
console.log(arr);
const result = mergeSort(arr);
console.log(result);

7. 总结

8. 快排

/**
 * 快速排序
 * 1. 找一个作为基准(这里取第一个)
 * 2. 比它大的右边，比它小的左边
 * 3. 得到的数组重复1，2，直到剩一个元素为止
 * 4. 把所有数组concat即可
 */
function quickSort(a) {
	if (a.length <= 1) return a;

	let mid = 0;
	let midItem = a.splice(0, 1)[0];
	let left = [];
	let right = [];
	a.forEach(function(item) {
		if (item <= midItem) {
			left.push(item);
		} else {
			right.push(item);
		}
	});

	console.log(a);
	console.log(left);
	console.log(right);
	var _left = quickSort(left),
		_right = quickSort(right);
	return _left.concat(midItem, _right);
}

// 生成随机整数
function random(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
}

// 生成len长度的随机数组
function generateArr(len) {
	let arr = [];
	for (var i = 0; i < len; i++) {
		arr.push(random(1, len));
	}
	return arr;
}

const arr = generateArr(10);
const result = quickSort(arr);
console.log(arr);
console.log(result);

9. 一行实现快排

// 错误的，splice会修改原数组，每次都删第一个
function quickSort(a) {
	return a.length <= 1
		? a
		: quickSort(a.splice(1).filter(item => item <= a[0])).concat(
				a[0],
				quickSort(a.splice(1).filter(item => item > a[0]))
		  );
}
// 正确的，slice会取原数组的返回新数组，不会修改原数组
function quickSort(a) {
	return a.length <= 1
		? a
		: quickSort(a.slice(1).filter(item => item <= a[0])).concat(
				a[0],
				quickSort(a.slice(1).filter(item => item > a[0]))
		  );
}

10. 三项快排

基础快排是分两份，一份小于等于，一份大于。如果是[1,1,1,1,1,1,1,1]这种会一直快排下去，为了提高效率，这里再加一个等于。

function quickSort(arr) {
	if (arr.length <= 1) return arr;
	let target = arr.shift();
	let left = [];
	let right = [];
	let mid = [target];
	arr.forEach(item => {
		if (item < target) {
			left.push(item);
		} else if (item > target) {
			right.push(item);
		} else {
			mid.push(item);
		}
	});

	let _left = quickSort(left);
	let _right = quickSort(right);
	return _left.concat(mid, _right);
}

[qingfengmy]

http://www.cnblogs.com/zichi/p/4788953.html
https://juejin.im/post/5af4902a6fb9a07abf728c40#heading-8
https://www.cnblogs.com/zichi/p/4796727.html