作业排程问题

问题描述

Automobile factory with two assembly lines(汽车厂两条装配线)

– Each line has n stations: S1,1, . . . , S1,n and S2,1, . . . , S2,n(每条装

配线有n个工序站台)

– Corresponding stations S1, j and S2, j perform the same function

but can take different amounts of time a1, j and a2, j (每条装配线的

第j个站台的功能相同,但是效率不一致)

– Entry times e1 and e2 and exit times x1 and x2(上线和下线时间)

单源最短路径算法

问题描述

[button color=”success” icon=”” url=”https://git.tanknee.cn/tanknee/DataStruct" type=””]全文源码git地址[/button]

基于磁盘的带替换选择的合并排序

先替换选择，再进行外部合并排序。

算法分析

运行时间的计算分析

上界：$O(f(N))$

[scode type=”yellow”]堆排序思路[/scode]

1. 将传入的数组看作是一个没有完成的堆
2. 将堆整理排序成一个大顶堆
3. 将大顶堆最大的元素，也就是堆顶，与这个堆最后的元素进行交换
4. 然后视这个除刚刚交换的那个元素外的数组为一个堆，对它进行大顶堆标准检查，并将其整理成一个大顶堆
5. 有一点需要注意的是每次交换之后接下来需要接着排序的堆的大小需要减一！
6. 为了减小空间的占用，可以视交换到末尾的元素为已经出堆的元素，仅仅对这些元素之前的数组进行大顶堆检查。

[scode type=”yellow”]大顶堆概念[/scode]

​ 树是一种简单的数据结构，其插入查找的速度都相对均匀：O(logN)，这里用到的主要是二叉查找树binary search tree。

• 了解树在文件系统里的应用
• 计算算术表达式的值，如中缀表达式等
• 树是如何实现以O(logN)的平均时间进行查找操作，以及最坏时间O(logN)。

树的基本模型

根据算法图解一书写的两个算法：广度优先算法以及狄克斯特拉算法：

散列表

散列表在Python中也称作字典，通常的定义方式为： name = dict()