快排:Swift实现

2014-12-19
阅读 3 分钟
3.7k
将数组A[p..r]分割成子数组A[p..q-1]与A[q+1..r],满足A[p..q-1]中的元素都不大于A[q]且A[q+1..r]中的元素都不小于A[q]。(标兵q的选择后续在讨论)

贪心:Swift实现

2014-12-17
阅读 3 分钟
3.7k
求解最优化问题得算法通常需要经过一系列得步骤,每个步骤都面临多种选择。在许多最优化问题上使用动态规划其实会有杀鸡用牛刀的感觉。贪心算法(greedy algorithm)保证每一步都作出当时看起来的最佳的选择,换句话说就是保证局部最优选。

动态规划:Swift实现

2014-12-16
阅读 7 分钟
3.7k
类似点在于都是通过组合子问题的解来求解原问题。 不同点在于分治方法将问题划分为互不相交的子问题,递归的求解子问题;而动态规划在于子问题重叠的情况,不同子问题的解是递归进行的,反复的求解公共子问题。

堆排序:Swift实现

2014-12-11
阅读 1 分钟
3.2k
概述 堆排序(heapsort)具有空间原址性,任何时候只需要常数个额外的元素空间存储临时数据。整个算法的时间复杂度是O(nlgn)。 堆性质 1)近似的完全二叉树 2) {代码...} 3)最大堆 A[PARENT(i)] >= A[i] 4)最小堆 A[PARENT(i)] <= A[i] 堆应用 最大堆常用于构造优先队列 堆的几个基本操作 MAX-HEAPIFY 时间复杂...

分治:Swift实现

2014-12-11
阅读 4 分钟
2.8k
中心思想 Divide 分解规模较小且问题形式相同的多个子问题 Conquer 子问题继续递归后能被求解 Combine 合并解组合 栗子:求最大子数组问题的分治思想 条件与返回值 输入源:数组A[low..high] 返回:A[i..j] 要求 A[i] + A[i+1].. + A[j] = MAX 分治模式 1.尽可能的将原数组分解为规模大致相同的两个子数组(Divide),找...