【学习心得】数据结构与算法

概述

• 基本概念
• 常见数据结构
• 高阶数据结构
• 经典算法
• 参考

基本概念

数据结构，一组存储数据的结构；算法，一组操作数据的方法。
数据结构是为算法服务的，算法要作用于特定的数据结构。
数据结构和算法解决的问题：如何让代码运行得更快，如何让代码更省存储空间。

• 常见数据结构：数组、链、栈、队列、散列表、二叉树、堆、跳表、图、树等
• 经典算法：递归、排序、二分查找、搜索、哈希算法、分治算法、回溯算法、动态规划、字符串匹配算法等
• （渐进）时间复杂度：T(n) = O(f(n))
  • T(n)：表示代码的执行时间
  • n：表示数据规模的大小
  • f(n)：表示每行代码执行次数的总和
  • O：表示代码的执行时间与执行次数总和成正比
  • T(n) 表示代码执行时间随数据规模增长的变化趋势，其表示法指出了最糟糕情况下的运行时间
  • 时间复杂度为 O(logn) 的算法：二分查找，红黑树查找，欧几里得算法，幂运算
  • 时间复杂度为 O(nlogn) 的算法：快速排序，归并排序，堆排序
• （渐进）空间复杂度：示算法的存储空间与数据规模之间的增长关系

常见数据结构

• 数组
  • 是一种线性表数据结构，用一组连续的内存空间，来存储一组具有相同类型或不同类型的数据，支持随机访问
  • 如何改善数组低效的插入和删除？
  • 数组寻址公式
    • 一维数组：a[k]_address = base_address + k * type_size
    • 二维数组：a[i][j]_address = base_address + (i * n + j) * type_size
  • JavaScript 相关数组方法
    • mutated：push, unshift, pop, shift, splice, reverse, sort, arr[i] = ...
    • immutated：concat, [...arr], map, filter, slice, reduce ...
• 链表
  • 不需要一块连续的内存空间，通过指针将一组零散的内存块串联起来使用
  • 常见的链表结构：单链表，双向链表，循环链表
  • 链表中的删除操作：删除节点中只等于某个定值的节点；删除给定指针的节点
  • 将某个变量赋值给指针，实际上就是将该变量的地址赋值给指针，即指针中存储了该变量的内存地址
  • 留意边界情况：链表为空；链表只包含一个节点；链表只包含两个节点；头尾节点的处理
• 栈
  • 栈是一种操作受限的线性表。虽然操作不够灵活自由，但使用时比较不可控
  • 使用场景：只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性
  • 应用场景：
• 队列
  • 队列也是一种操作受限的线性表。具有先进先出、后进后出的特性
  • 使用场景：对于大部分资源有限的场景，当没有空闲资源时，基本上可以通过队列来实现请求排队
  • 应用场景：阻塞队列（生产者-消费者模型），循环并发队列（加锁）
  • 队列存储的实现方式
    • 基于链表的实现：可实现一个支持无限排队的无界队列，但是可能会导致过多的请求排队等待，请求处理的响应时间过长
    • 基于数组的实现：队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝

高阶数据结构

• 堆
• 跳表
• 哈希表
• 二叉树

经典算法

• 动态规划
• 分治算法
• 贪心算法
• 回溯算法
• 分支界限法

参考

• 数据结构与算法学习心得 (opens new window)