1.
时间复杂度、空间复杂度
答案：
在描述算法复杂度时，经常用到O(1)、O(n)、O(logn)、O(nlogn)来表示对应算法的时间复杂度，也可以用于表示对应算法的空间复杂度
O后面的括号中有一个函数，指明算法的耗时/耗空间与数据增长量之间的关系，其中的n代表输入数据的量
1)O(1)最低的时间复杂度，也就是耗时与输入数据大小无关，无论输入数据增大多少倍，耗时都不变。哈希算法就是典型的O(1)时间复杂度，无论
数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）
2)O(n)代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法
3)O(n^2)代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的时间复杂度为O(n^2)的算法，
对n个数排序，需要扫描nxn次
4)O(logn)代表数据量增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。
二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要8次就可以找到目标
5)O(nlogn)代表数据量增大n倍时，耗时增加n乘logn倍，当数据增大256倍时，耗时增大256 * 8 = 2048倍。这个复杂度高于线性低于平方，归并排序
就是O(nlogn)的时间复杂度
2.
实现一个字符串匹配算法，从长度为n的字符串S中，查找是否存在字符串T，T的长度是m，若存在返回所在位置？
答案：
普通方法
function violenMath(S, T) {
let sLen = S.length;
let tLen = T.length;
let i = 0;
let j = 0;
while (i < sLen && j < tLen) {
if (S[i] == T[j]) {
i ++;
j ++;
} else {
i = i - j + 1;
j = 0;
}
}
if (j == tLen) {
return i - j;
}
return -1;
}
KMP算法
3.
二分法排序实现
4.
归并排序实现
归并排序是采用分治法的一个非常典型的应用。归并排序有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个
有序数组合并成一个更大的有序数组
function mergeSort(arr) {
let len = arr.length;
if (len <= 1) {
return arr;
}
let middle = Math.floor(arr.length / 2);
let left = mergeSort(arr.slice(0, middle));
let right = mergeSort(arr.slice(middle, len));
return merge(left, right);
}
// 用于对两个子数组进行排序合并
function merge(left, right) {
let i = 0;
let j = 0;
let ret = [];
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
ret.push(left[i]);
i++
} else {
ret.push(right[j]);
j++;
}
}
ret = ret.concat(left.slice(i));
ret = ret.concat(right.slice(j));
return ret;
}
mergeSort([38, 27, 43, 3, 9, 82, 10]); // 结果：[3, 9, 38, 27, 43, 82, 10]
归并排序是一种稳定的排序算法，时间复杂度O(nlogn)
参考：https://www.jianshu.com/p/e3cb5423f89c