1 Classify

1.1 比较类-非线性时间-排序

  • 交换类排序:快速排序、冒泡排序
  • 插入类排序:简单插入排序、希尔排序
  • 选择排序:简单选择排序、堆排序
  • 归并排序:二路归并排序、多路归并排序

1.2 非比较类-线性时间-排序

  • 计数排序: O(n), 特殊的桶排序, 此时桶的个数最大, 创建maxvalue-minxvalue+1的数组
  • 基数排序: 利用位数从低位到高位, 不断的进行数值排序
  • 桶排序: 将数组分配到有限数量的桶中, 之后再对桶分别排序.
  • 索引排序: 在排序过程中, 如果数据元素本身很大, 不断的赋值移动消耗资源, 则可将数据移动更改为索引移动, 减少复杂度

1.3 内存

  • 内排序: 待排序的记录个数少, 整个排序过程都在内存中
  • 外排序: 采用外部文件排序技术

1.4 性能与分类图解

性能:

algorithm performance

分类:

algorithm classify

性能分类总结:

  • 平方阶:O(n2),简单排序(直接插入、直接选择、冒泡)
  • 线性对数阶:O(nlgn),二分思维– (快速排序、堆排序、归并排序)
  • O(n1 +£):£值范围[0..1],例如n1.2,n2等阶,希尔排序
  • 线性阶:O(n),空间换时间(桶排序、基数排序)

排序选择:

  • 基本正序时——简单排序最适合
  • n较大时——快排、堆排、归并

2 分治法

2.1 Intro

将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,
然后将这些子问题的解组合为原问题的解.

2.2 Feature

  • 问题的数据缩小到一定的规模之后, 有较好的解决办法
  • 问题可以分解为若干个较小规模的相同问题, 即最优子结构性质
  • 问题分解后的若干小问题解可以合并为该问题的解
  • 问题的若干个小问题是相互独立

2.3 Step

  1. Divide: 将问题分解为若干小规模的相同问题
  2. Conquer: 递归求解各个小问题, 如果小问题足够小, 则直接计算, 否则递归
  3. Combine: 将所有子问题的解合并

2.4 Algorithm

  • 归并排序: 将数组分解, 解决, 合并
  • 快速排序: 存在一点分治的思维, 将以某一个值为基准, 对整个数组进行分解, 只不过没有合并的过程

3 归类法

3.1 Intro

有点类似分治法, 对于某一个问题, 将数据首先进行整合分类, 以便打到最初的目的, 编程
中实际上也经常是该思路, 各个模块实际上都是对原始数据进行归纳整合, 只不过没有
那么明显而已.

3.2 Handle

如何让同类数据存储在一个相同的地方? 对于单位数据, hash天生自带该功能, 对于复合
数据那么需要一定的算法, 对原始数据进行整合归类.

3.3 Algorithm

  • 桶排序: 有点类似归类
  • 基数排序: 按照位数来进行归类

4 Example

4.1 出现次数最多纪录

问题: 海量日志数据, 提取出现次数最多的 IP.

分析: 注意到ipv4的位数(32位), 如果载入所有ip到hash中, 最多有2^32个记录, 需要采用分而治之的思想, 将ip的地址 Hash(ip) % 1024, 即将ip分别存储到1024个文件中, 这样每一个文件最多包含: 2^32 / 1024 == 4MB

步骤(分治 + Hash);

  • 分治, Hash(ip) % 1024, 海量ip分配到1024个文件中, 每一个文件大概4MB 内存
  • 对于每一个小文件, 构建key->value的映射, 其中ip为key, 记录出现次数最多的ip
  • 对于1024个小文件筛选出次数最多的 IP 值, 因为所有的相同IP利用hash都会映射到同一个文件中.

4.2 出现次数前100的记录

问题: 海量日志数据, 提取出现次数最多的前100 IP.

分析: 该问题和3.1的区别在于提取多个数据. 即对每一个小文件, 提取前100项数据, 得到数据项: 1024 * 100, 最后对这个1024个文件进行归并排序

步骤:

  • 分支
  • 对于小文件, 利用trie/hash_map进行分类, 记录出现次数最多的100个ip
  • 进行归并排序

4.3 对多个大文件进行频度统计

问题: 有10个文件, 每一个文件1G, 每个文件的每一行存放的都是用户的query, 每个文件的query都可能重复, 需要按照query对文件进行排序.

最终场景: 10个文件, 其中文件中的query都有有序的, 并且文件a的最小频度 > 文件b的最大频度

分析: TOP K 算法, 首先需要对数据进行归类, 对相同的query进行合并, 利用hash进行归类, 其次对归类的每一个文件进行排序操作, 最后对所有文件进行归并排序. 这里就使用到归类法.

步骤:

  • 首先, 对10个文件依次进行hash(query) % 10, 这里假设hash的数据都能平均的分到10个文件里面, 得到10个归类后的文件
  • 其次, 找一个2G 内存的机器, 对每一个文件进行排序, 输出query-query_count
  • 再次, 对10个文件进行归并排序

4.4 查找a是否在40亿个不重复的unsigned int整数集中

问题: 对于40亿个不重复的unsigned int整数, 未排过序, 任意给定一个数, 如何快速判断
是否在改集合中.

最终场景: 快速的查找某一个数

分析: 一般, 查找算法的前提都是基于排序算法, 只有对目标数据进行排序, 后续的查找
算法才能更加方便和快捷. 一般而言, 树结构对于查找算法最适合, 考虑到整数的特殊性,
这里可以按照位数来将一个大文件改造成一棵小文件树结构.

步骤:

  • 首先, 对40亿个数进行分类, 最高位0-A 文件, 最高位1-B 文件, 此时两个文件大小20亿条数据
  • 其次, 重复上述步骤, 构建一棵哈夫曼树结构(霍夫曼编码)
  • 再次, 查找, O(logN)

4.5 逆序对组合

问题: 对于一个长度为n的整数数组A, 找出”逆序对”的个数, 对于下标i,j, 当i>j,
A[i]小于A[j], 则(A[i], A[j])称为逆序对

最终场景: 最终会列出所有的逆序对, 并且是有序的.

分析: 如果使用暴力方式, 那么对于每一个值a, 比较其他N-1个值, 重复 N 次, 整个时间复杂度为 O(N^2). 如果采用分治思想, 以mod中间点进行数组切割, 递归统计: 左半部分, 右半部分, 跨越中点的个数(即i在左边, j在右边的合法值队), 最后进行归并, 此时归并排序
改变的位置值实际上不影响最终的结果, 因为当前已经排序好的组合在位置上是一个整体,
即对外是一个下标: set-i, 其他递归集也是这样的: set-j, set-x.

步骤:

  • divide: 对数组进行对半切分, 每一个子数组都是一个逆序对组合题目
  • conquer: 递归的对子数组进行对半切分
  • combine: 对两个已经排好序的子数组进行归并排序, 同时记录逆序对, 注意, 这里主要工作量在归并排序, 以及记录逆序对这里