算法与数据结构

数据结构与算法图解(图灵书系)

复杂度

• 时间复杂度 —— 比较各自的步数 （平均复杂度，最差复杂度）
• 空间复杂度 O

散列表

• 使用散列表时需要权衡：既要避免冲突，又要节约空间。理想的负载因子是0.7（7个元素/10个格子）

栈

• 栈 后进先出(Last In, First Out) 像子弹夹，压栈
• 队列 先进先出(First In, First Out) 像排队，入队

堆

B树

红黑树

二三四树

递归

• 计算机用栈来记录每个调用中的函数，这个栈就叫做调用栈——避免调用路径太深，会占用过多内存

  无限递归会一直占用内存，直至内存溢出

• 递归十分适用于那些无法估计计算深度的问题（如便利文件目录）
• 快速排序，使用递归

基于结点的数据结构

• 链表，双向链表使队列插入和删除都为O(1)
• 二叉树 既能维持元素的顺序，又能快速地查找、插入、删除—— 比链表复杂，但比链表更有用
• 图（有向图、无向图）—— 广度优先搜索、深度优先搜索，最短路径问题——Diskstra算法