LynDocs

外观

算法复杂度 ​

认识算法复杂度 ​

对于同一个问题，我们往往其实有很多种解决它的思路和方法，也就是可以采用不同的算法

  • 但是不同的算法，其实效率是不一样的

举个例子（现实的例子）:在一个庞大的图书馆中，我们需要找一本书。在图书已经按照某种方式摆好的情况下（数据结构是固定的）

  • 方式一：顺序查找
    • 一本本找，直到找到想要的书（累死）
  • 方式二：先找分类，分类中找这本书
    • 先找到分类，在分类中再顺序或者某种方式查找
  • 方式三：找到一台电脑，查找书的位置，直接找到
    • 图书馆通常有自己的图书管理系统
    • 利用图书管理系统先找到书的位置，再直接过去找到

顺序查找 ​

方式一: 顺序查找

  • 这种算法从头到尾遍历整个数组，依次比较每个元素和给定元素的值
  • 如果找到相等的元素，则返回下标；如果遍历完整个数组都没找到，则返回 -1
typescript
function sequentSearch(array: number[], num: number) {
  for (let i = 0; i < array.length; i++) {
    const item = array[i]
    if (item === num) return i
  }
  return -1
}

二分查找 ​

方式二：二分查找

  • 这种算法假设数组是有序的，每次选择数组中间的元素与给定元素进行比较
  • 如果相等，则返回下标；如果给定元素比中间元素小，则在数组的左半部分继续查找
  • 如果给定元素比中间元素大，则在数组的右半部分继续查找
  • 这样每次查找都会将查找范围减半，直到找到相等的元素或者查找范围为空
typescript
function binarySearch(array: number[], num: number) {
  // 1.定义左边的索引
  let left = 0
  // 2.定义右边的索引
  let right = array.length - 1
  // 3.开始查找
  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    const midNum = array[mid]
    if (midNum === num) {
      return mid
    } else if (midNum < num) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return -1
}

测试效率 ​

typescript
import sequentSearch from './1.顺序查找'
import binarySearch from './2.二分查找'

const MAX_LENGTH = 10 * 1000 * 1000
const nums = new Array(MAX_LENGTH).fill(0).map((_, i) => i)
const num = MAX_LENGTH / 2

const startTime1 = performance.now()
const index1 = sequentSearch(nums, num)
const endTime1 = performance.now()
console.log('索引为：', index1, '。消耗的时间：', endTime1 - startTime1)

const startTime2 = performance.now()
const index2 = binarySearch(nums, num)
const endTime2 = performance.now()
console.log('索引为：', index2, '。消耗的时间：', endTime2 - startTime2)

大O表示法 ​

大 O 表示法（Big O notation）英文翻译为大 O 符号（维基百科翻译），中文通常翻译为大 O 表示法（标记法）

  • 这个记号则是在德国数论学家爱德蒙·兰道的著作中才推广的，因此它有时又称为兰道符号（Landau symbols）
  • 代表 "order of..." (....阶) 的大 O，最初是一个大写希腊字母 "O" (omicron) ，现今用的是大写拉丁字母 "O"

大 O 符号在分析算法效率的时候非常有用

举个例子，解决一个规模为 n 的时间所花费的时间（或者所需步骤的数目）可以表示为：T(n) = 4n^2 -2n + 2

  • 当 n 增大时，n^2 项开始占据主导地位，其他各项可以被忽略

举例说明：当 n=500

  • 4n^2 项是 2n 项的 1000 倍大，因此在多数场合下，省略后者对表达式的值的影响是可以忽略不计的
  • 进一步看，如果我们与任意其他级的表达式比较，n^2 的系数也是无关紧要的

这样，针对这个例子 T(n) = 4n^2 -2n + 2 大 O 表示法就几下剩余的部分，写作：T(n) = O(n^2)

  • 具有 n^2（平方阶）的时间复杂度，表示为：O(n^2)

函数阶 ​

符号名称
O(1)常数（阶）
O(log^n)对数（阶）
O(n)线性，次线性
O(n log^n)线性对数，或对数线性、拟线性、超线性
O(n^2)平方
O(n^c)多项式，有时叫作 "代数"（阶）
O(c^n)指数，有时叫做 "几何"（阶）

image-20230817144939852

空间复杂度 ​

空间复杂度指的是程序运行过程中所需要的额外存储空间

  • 空间复杂度也可以用大 O 表示法来表示
  • 空间复杂度的计算方法与时间复杂度类似，通常需要分析程序中需要额外分配的内存空间，如数组、变量、对象、递归调用等

举个栗子

  • 对于一个简单的递归算法来说，每次调用都会在内存中分配新的栈帧，这些栈赖占用了额外的空间
    • 因此，该算法的空间复杂度是 O(n)，其中 n 是递归深度
  • 而对于迭代算法来说，在每次迭代中不需要分配额外的空间，因此其空间复杂度为 O(1)

当空间复杂度很大时，可能会导致内存不足，程序崩溃

在平时进行算法优化时，我们通常会进行如下的考虑：

  • 使用尽量少的时间（优化空间复杂度）
  • 使用进行少的时间（优化时间复杂度）
  • 特定情况下：使用空间换时间或时间换空间
数组链表
访问O(1)O(n)
查询O(n)O(n)
插入O(n)O(1)
删除O(n)O(1)

数组是一种连续的存储结构，通过下标可以直接访问数组中的任意元素

  • 时间复杂度：对于数组，随机访问时间复杂度为 O(1)，插入和删除操作时间复杂度为 O(n)
  • 空间复杂度：数组需要连续的存储空间，空间复杂度为 O(n)

链表是一种链式存储结构，通过指针链接起来的节点组成，访问链表中元素需要从头结点开始遍历

  • 时间复杂度：对于链表，随机访问时间复杂度为 O(n)，插入和删除操作时间复杂度为 O(1)
  • 空间复杂度：链表需要为每个节点分配存储空间，空间复杂度为 O(n)

在实际开发中，选择使用数组还是链表，需要根据具体应用场景来决定

  • 如果数据量不大，且需要频繁随机访问元素，使用数组可能会更好
  • 如果数据量大，或者需要频繁插入和删除元素，使用链表可能会更好

常备不懈，才能有备无患