为什么需要 时间复杂度分析
如果 将程序跑一遍,通过统计/监控 得到算法执行的时间和占用的内存(事后统计法)
这样做得到得数据
1.受测试环境影响 2.受数据规模的影响很大
什么是 大O复杂度表示法
大O 时间复杂度,也称为 渐进式时间复杂度,表示 代码执行时间 随数据规模增长
T(n) = O(n²)
T(n) 总执行时间, F(n) 每行代码总执行次数
如何进行时间复杂度分析
一段代码
1.只关注循环执行次数最多的一段代码
2.只关注量级最大的那段代码
时间复杂度分析规则类别
最好/最坏时间复杂度:在最理想/最糟糕 的情况下的时间复杂度(best/worst case time complexity)
平均情况时间复杂度:在平均 的情况下的时间复杂度(average case time complexity)
加权平均时间复杂度/期望时间复杂度:计算 平均情况时间复杂度 时,加入了概率权重
均摊时间复杂度:摊还分析/平摊分析,针对存在规律的 平均情况时间复杂度
的一种分析思想
例如 每一次O(n)的操作,会紧跟着n-1次O(1)的操作,将O(n)均摊在n-1次的O(1)上,最终 时间复杂度为O(1)
什么是 空间复杂度
空间复杂度,O(1),O(n),O(n²),表示 算法运行需要的储存空间 与 数据规模 之间 的增长关系
什么是数组
线性表结构 以及 连续的内存空间 相同的数据类型,使数组支持 高效的 下标 随机访问 的能力
缺点:
为了保持数据 在内存空间的连续性，插入 删除 操作都会伴随数据搬运。
插入优化:若数组无序，第k位数据移动到末尾，要插入的数据移动到，k位
删除优化:标记删除位置，当数组无储存空间时，统一清空重排。
但是在 Javascript中不一定是连续分配的,而可能是 哈希映射的方式 存在的。
JS中的数组底层有两种表现形式 fast 和 slow
fast: 就是正常的数组,具有固定的长度,并自带扩容功能,内存不够用时申请新地址并进行拷贝
slow: 其实是个map,散列表 哈希表,键为0 1 2 3,值为数据.
什么是链表
储存: 由 结点 组成,包含 数据 和 后继指针,数组需要连续的内存空间,链表的储存用的是 零散的内存块
储存: 数组 的空间在 栈 中分配,链表 的空间在 堆 中分配
插入删除: 数组的 插入删除 操作需要保持 内存的连续性 做数据搬移,链表的 插入删除 不需要做数据搬移,时间复杂度为O(1)
查找: 数组 下标随机读取 时间复杂度为O(1),链表 查找 为O(n)
单链表: 存在 头结点 和 尾结点,尾结点的后继指针指向空地址 null.
循环链表: 尾结点指向头结点,适合处理具有环形结构特点问题,约瑟夫问题.
双向链表: 具有 前驱指针 (prev)指向前面的结点,支持O(1)找到前驱结点
数组 可以利用CPU缓存机制,做到快速读取.CPU缓存机制就是CPU读数据是一段一段读的.
CPU缓存机制是为了弥补读取内存速度过慢CPU计算速度过快之间的差距
数组链表的优缺点
数组的优点: 简单易用,随机访问效率高,查找速度快
数组的缺点: 插删效率低,空间利用率低,空间大小固定,空间必须是连续的内存空间
链表的优点: 插删效率高,内存利用率高,空间大小不固定
链表的缺点: 内存消耗更多,随机访问效率低
数组 一声明就要占用固定大小空间
什么是栈
只允许在一端插入和删除数据,操作受限的 线性表数据结构
特性:先进后出,后进先出
分为 顺序栈,链式栈 两种
应用: 函数调用栈 表达式求值 括号匹配 浏览器的前进后退
什么是队列
只允许在一端插入 另一端删除,操作受限的 线性表数据结构
特性: 先进先出,后进后出
分为 顺序队列,链式队列 两种
队列需要两个指针,标记队列头 和 尾
排序
冒泡排序: 右侧有序,外层记录左边界，内层从左往右,0 length, hasChanged, 0 -i-1,全是j
空间复杂度为 O(1),是 原地排序算法,
相邻元素大小相等时不会进行交换 是 稳定的排序算法,
时间复杂度 为 O(n²)
插入排序: 左侧有序,外层记录右边界，内层从右往左,1 length, temp j, i-1 0
空间复杂度为 O(1),是 原地排序算法,
发现值相同的元素时插入 是 稳定的排序算法,
时间复杂度 为 O(n²) (n轮,每轮移动n个数)
选择排序: 左侧有序,外层记录左边界，内层从右往右,0 length-1, minIndex, i+1 length
空间复杂度为 O(1),是 原地排序算法,
是 不!稳定的排序算法,
任何情况时间复杂度 为 O(n²)
插入排序 比 冒泡排序 性能更好
插入排序和冒泡排序的元素交换次数都是原始数据的逆序度
但每次交换 冒泡排序需要 3个赋值操作，插入排序只需要1个
冒泡排序
// 冒泡排序
const bubbleSort = (arr) => {
// length <= 1 直接return
if (arr.length <= 1) return
for (let i = 0; i < arr.length; i++) {
let hasChange = false
// 每次冒泡最末尾的数已经位于正确的位置,后续不需要参与比较所以-i-1
for (let j = 0; j < arr.length - i - 1; j++) {
// 从小到大进行排序
if (arr[j] > arr[j + 1]) {
const temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
hasChange = true
}
}
// 如果某次冒泡没进行任何交换 说明所有元素已经到位
if (!hasChange) break
}
console.log(arr)
}
const test = [4, 5, 6, 3, 2, 1]
bubbleSort(test)插入排序
// 插入排序
const insertionSort = (arr) => {
if (arr.length <= 1) return
for (let i = 1; i < arr.length; i++) {
const temp = arr[i]
let j = i - 1
// 这里是 >= 0
for (j; j >= 0; j--) {
// 这里是和temp比大小，不是arr[i]
if (arr[j] > temp) {
arr[j + 1] = arr[j]
} else {
// 找到比j小的数之后要break,j不需要减小了
break
}
}
// temp放这个数后面(j+1)
arr[j + 1] = temp
}
console.log(arr)
}
const testSort = [4, 1, 6, 3, 2, 1]
insertionSort(testSort)选择排序
// 选择排序
const selectionSort = (arr) => {
if (arr.length <= 1) return
// 需要注意这里的边界, 因为需要在内层进行 i+1后的循环，所以外层需要 数组长度-1
for (let i = 0; i < arr.length - 1; i++) {
let minIndex = i
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
const temp = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
}
console.log(arr)
}
const testSelect = [4, 8, 6, 3, 2, 1, 0, 12]
selectionSort(testSelect)快速排序/归并排序
快速排序: 时间复杂度O(nlogn),空间复杂度O(1),不稳定的排序算法,原地排序
归并排序: 时间复杂度:O(nlogn),空间复杂度:O(n), 稳定的排序算法,非原地排序
快速排序 极端情况下时间复杂度退化成O(n²),例如选中有序数组的最后一位做为pivot
防止极端情况:
三数取中法(每次从要排序的区间中 首 尾 中 取数 中值作为pivot,可5数取中,等)
随机法(每次从要排序的区间中随机选择pivot)
归并排序 相等的元素,left数组内的数具有优先权,保证了其稳定排序
归并 自下而上, 快排 自上而下
快速排序
const quickSort = (arr, left, right) => {
if (left < right) {
let pivot = right
let partitionIndex = partition(arr, pivot, left, right)
quickSort(arr, left, partitionIndex - 1)
quickSort(arr, partitionIndex + 1, right)
}
}
const partition = (arr, pivot, left, right) => {
const pivotVal = arr[pivot]
let startIndex = left
for (let i = left; i < right; i++) {
if (arr[i] < pivotVal) {
swap(arr, i, startIndex)
startIndex++
}
}
swap(arr, startIndex, pivot)
return startIndex
}
const swap = (arr, i, j) => {
const temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
const testArr = []
let i = 0
while (i < 10) {
testArr.push(Math.floor(Math.random() * 1000))
i++
}
console.log('排序前:', testArr)
quickSort(testArr, 0, testArr.length - 1);
console.log('排序后:', testArr)归并排序
const mergeSort = (arr) => {
if (arr.length <= 1) return arr
const middle = Math.floor(arr.length / 2)
const left = arr.slice(0, middle)
const right = arr.slice(middle)
return mergeArr(mergeSort(left), mergeSort(right))
}
const mergeArr = (left, right) => {
let temp = []
let leftIndex = 0
let rightIndex = 0
while (left.length > leftIndex && right.length > rightIndex) {
if (left[leftIndex] <= right[rightIndex]) {
temp.push(left[leftIndex])
leftIndex++
} else {
temp.push(right[rightIndex])
rightIndex++
}
}
return temp.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
}
let arr = []
let count = 10
while (count > 0) {
arr.push(Math.floor(Math.random() * 100))
count--
}
console.log('排序前:', arr)
console.log('排序后:', mergeSort(arr));桶排序(BucketSort)
桶排序实际上是一种思想,主要用于排序 大批量数据(10GB),
进行外部排序(数据储存在外部磁盘中),
进行分批次排序
先扫描一遍文件,确定数据范围,如1-100
首先,划分每个’桶’内存放的数据区间,如1-10,11-20…91-100
然后,扫描数据将数据存放在属于自己范围内的桶内
再次,依次对各个桶进行排序
最后,按顺序 直接拼接 各桶数据.
数据量大可继续分桶,数据不均匀可桶内再分桶
二分查找(BinarySearch)
// 数组必须有序 不存在重复
const BinarySearch = (sortedArr, target) => {
if (sortedArr.length === 0) return -1
let low = 0
let high = sortedArr.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (target === sortedArr[mid]) {
return mid
} else if (target < sortedArr[mid]) {
high = mid - 1
} else {
low = mid + 1
}
}
return -1
}
const arr = [1, 4, 5, 6, 7, 8, 10, 11, 23, 42, 44, 54, 56, 77, 102]
console.log(BinarySearch(arr, 44))
console.log(BinarySearch(arr, 1))
console.log(BinarySearch(arr, 102))
console.log(BinarySearch(arr, 1111))注意循环退出条件是 low <= high
注意 high = mid - 1,low = mid + 1,没这个 1 可能会死循环(high=low时)
(low + high) / 2 可优化为 low + (high - low) / 2,防止high+low溢出
必须是顺序表结构(数组),必须是有序数据
理论上二分查找可以解决的问题,散列表 二叉树都能解决,但是需要更多额外空间
所以限制内存空间及 数据量较大时 使用 二分查找
查找k次,2的k次方能覆盖n个元素
时间复杂度O(logn)
