# 一、疑惑解答

# 1、什么是数据结构与算法?

  数据结构与算法的本质就是 一门专门研究数据如何组织、存储和操作的科目,但官方并没有明确的定义。

其中,数据操作/使用的效率 与 数据的组织/存储方式紧密相关(比如生活中的快递站)。

  Pascal 之父 —— Nicklaus Wirth 曾就凭借:算法 + 数据结构 = 程序(Algorithm + Data Structure = Programs)这一著名公式获得了 图灵奖。

# 2、为什么要学习数据结构与算法?

  在常规的开发和学习中,可能我们很少直接接触到 数据结构与算法。但其实它无处不在:

  • 常用的前端框架(比如 Vue、React 的源码)中就大量使用了栈结构、队列结构等
  • 在 webpack 源码中,也可以看到队列、栈结构、树结构、Graph 图结构
  • 还有场景的实现语言或者引擎本身也需要大量的数据结构:哈希表结构、队列结构(微任务队列、宏任务队列)
  • 前端开发中更常见的数据结构还有:DOM Tree(树结构)、AST(抽象语法树)

# 3、常见的数据结构有哪些?

提示

  其中 数组(Array)、栈(Stack)、队列(Queue)、链表(LinkedList)都属于线性结构。

# 4、常见的算法有哪些?

  算法是一组用于执行特定任务或解决特定问题的有序步骤。

  它是一种计算过程,可以接受一些输入,经过一系列定义明确的操作,产生输出结果。

  Algorithm 这个单词的本意就是解决问题的办法/步骤逻辑,数据结构的实现,离不开算法。

# 二、算法复杂度

# 1、顺序查找

时间复杂度:O(n)

export function sequenceSearch(array: number[], target: number) {
  for (let i = 0; i < array.length; i++) {
    const item = array[i]
    if (item === target) {
      return i
    }
  }
  return -1
}

# 2、二分查找

  图示:

时间复杂度:O(log n)

// 参考:https://simple.wikipedia.org/wiki/Binary_search
export function binarySearch(array: number[], target: number) {
  // 索引
  let leftIndex = 0
  let rightIndex = array.length - 1

  while (leftIndex <= rightIndex) {
    let midIndex = Math.floor((leftIndex + rightIndex) / 2)

    // 中间item
    const midItem = array[midIndex]

    if (midItem === target) {
      return midIndex
    } else if (midItem < target) {
      leftIndex = midIndex + 1
    } else {
      rightIndex = midIndex - 1
    }
  }

  return -1
}

# 3、时耗测试

import { sequenceSearch, binarySearch } from '../Search'

// 一个sorted list 排序列表
// const array = [17, 22, 33, 54, 57, 136, 176, 366, 382]
const array = new Array(10000000).fill(0).map((_, index) => index)
const target = 7000000

// 顺序查找
const timeStart = performance.now()
const index_by_sequence = sequenceSearch(array, target)
const timeEnd = performance.now()

console.log(index_by_sequence, '顺序查找-时耗:', timeEnd - timeStart, '毫秒') // 7000000 顺序查找-时耗: 9.334400057792664 毫秒

// 二分查找
const timeOn = performance.now()
const index_by_binary = binarySearch(array, target)
const timeoff = performance.now()

console.log(index_by_binary, '二分查找-时耗:', timeoff - timeOn, '毫秒') // 7000000 二分查找-时耗: 0.1557999849319458 毫秒

# 三、大 O 表示法

参考:https://www.freecodecamp.org/news/big-o-notation-why-it-matters-and-why-it-doesnt-1674cfa8a23c/

# 1、时间复杂度

  • O(1):哈希表
  • O(log n):Tree 结构(二分查找……)
  • O(n):顺序查找

# 2、空间复杂度

  空间复杂度很大时,可能会导致内存不足,进而程序奔溃(比如大量递归)

通常不用考虑,有时我们甚至还有 空间换取时间 的需求(比如:动态规划)。

# 3、数据结构对比 🎈

参考:https://www.bigocheatsheet.com/

# 4、算法对比

参考:https://www.bigocheatsheet.com/

更新于 : 7/8/2024, 10:21:14 AM