数据结构和算法

知识地图

复杂度分析

复杂度分析的必要性

• 提前预测程序的性能，选择更优的算法

• 避免事后统计

  • 测试结果依赖硬件环境
  • 测试结果依赖数据规模

时间复杂度

• 代码执行时间随数据规模增长的变化趋势
• 最好时间复杂度
• 最坏时间复杂度
• 平均时间复杂度

空间复杂度

数组

特点

• 线性表
• 连续的内存空间
• 存储类型相同的数据

操作

• 查找

  • 数组支持根据下标随机访问元素，O(1)

• 插入

  • 向某个位置插入元素时，需要将index全部后移一位。O(n)
  • 优化：当不考虑顺序时，可以将插入位置的元素直接移到末尾，插入元素放在插入位置

• 删除

  • 删除某个位置，将index后得元素全部前移一位.O(n)
  • 优化：标记删除的元素，稍后全部一次移动删除

ArrayList

• Java中ArrayLIst对于基础数组进行封装
• 初始容量为10，会扩展为1.5倍

排序

冒泡

• 只操作相邻的两个元素，看是否满足大小关系。如果不满足就交换位置。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次就完成n各数据的排序工作

插入

• 取未排序区间中的元素，在已排区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序，重复直到未排序区间中元素为空

选择

• 取未排序区间中的最小元素，插入到已排序区间的末尾，即和未排序区间的第一个元素交换位置

归并排序

• 如果要排序一个数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起
• 最好、最坏、平均时间复杂度都是O(nlogn)

快速排序

• 如果要排序数组中下标从p到r之间的一族数据，选择p到r之间的任意一个数据作为分区点，将大于分区点的放到右边，将分区点放到中间
• 大部分的时间复杂度是O(nlogn)，极端情况下退化为O(n2)
• 原地不稳定的排序算法
• 如何用快排思想在O(n)内查找第K大元素？

桶排序

• 将要排序的数组分到几个有序的桶里，每个桶里的数据再单独进行排序。然后再依次取出，组成的序列就是有序的了

• 容易数据划分成m各桶，每个桶内数据比较均匀。如果全部划分到一个桶里，就退化为O(nlogn)的排序算法

• 桶排序适合用在外部排序中

  • 外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中
  • 10GB的订单数据，希望按照订单金额进行排序？

计数排序

• 场景：排序的n个数据所处的范围不大。最大值为k，将数据划分为k个桶，桶内不需要排序

基数排序

• 基数排序是在数据长度很长，或者元素很多时候，每个元素依赖桶排序或计数排序，然后就能够将整体排序好

如何根据年龄给100万用户排序？

如何选择排序算法

• 小规模

  • 选择O(n2)的算法

• 大规模

  • 选择O(nlogn)的算法

• 子主题 3

查找

假设有1000万个整数数据，每个数据占8个字节，如何设计数据结构和算法，快速判断每个整数是否出现在这1000万数据中？

二分查找

• 时间复杂度O(logn)

• 二分查找是按照下标随机访问数据的，因此依赖的是数组。而链表会退化为O(n)

• 数组必须是有序的，而排序时间复杂度是O(nlogn)，如果没有频繁插入、删除，一次排序，多次查找。如果比较频繁就不适用了

• 数据量太小，直接顺序遍历就可以了

• 数据量太大，因为依赖的是数组，需要连续内存，也不适合

• 问题

  • 查找第一个值等于给定值的元素
  • 查找最后一个值等于给定值得元素
  • 查找第一个大于等于给定值的元素
  • 查找最后一个小于等于给定值的元素

链表

队列

栈

树

图