- 博客(4)
- 收藏
- 关注
RSS订阅原创 【算法与数据结构】快速排序算法
【算法与数据结构】快速排序算法快速排序算法一. 分区问题普通分区法霍尔分区法 (Hoare Partition Algorithm)荷兰国旗划分法 (Dutch National Flag Partition Algorithm)二. 快排的实现快排的时间与空间复杂度三. 改善快排的最坏时间复杂度k 阶统计量 (K-th Order Statistics) 和选择问题快速选择算法 ( Quickselect Algorithm)随机 pivot 选择 (Randomised Pivot Selection)
2021-01-08 12:27:10
248
原创 【算法与数据结构】算法分析 二
【算法与数据结构】算法分析 二1 简单排序算法1.1 选择排序1.2 插入排序2 算法的特性稳定排序 (Stable Sorting)在线算法 (Online Algorithms)就地算法 (In-place Algorithms)不变量是验证算法正确性的有力工具，我们经常会见到并且也是特别重要的便是循环不变量，这是在程序迭代过程或循环时产生的不变量。循环不变量可以帮助我们分析和建立许多简单排序算法的正确性，下面我们将以此为例进行探讨。本文将涵盖：使用不变量分析算法强与
2021-01-02 15:17:37
260
原创 【算法与数据结构】算法分析 一
【算法与数据结构】算法分析 一1 程序验证1.1 正确性讨论Case 1：key ∈ arrayCase 2: key ∉ array1.2 终止论证2 复杂度分析2.1 复杂度表示2.2 复杂度的衡量最佳，最坏和平均情况复杂度随机算法的复杂度当我们写程序时，我们通常会测试它们以确保其正确性，但测试一个程序只能证明它是否错误。为了证明一个程序总是有效的，我们需要使用更加数学化的方法。算法分析的两大重点是证明算法是正确的，以及确定算法使用的资源量 (时间和空间)。1 程序验证程序验证取决于两个主要原则
2020-12-28 20:05:07
105
原创 【算法与数据结构】算法分析 一
【算法与数据结构】算法分析 一1 程序验证1.1 正确性讨论Case 1：key ∈ arrayCase 2: key ∉ array1.2 终止论证2 复杂度分析2.1 复杂度表示2.2 复杂度的衡量最佳，最坏和平均情况复杂度随机算法的复杂度当我们写程序时，我们通常会测试它们以确保其正确性，但测试一个程序只能证明它是否错误。为了证明一个程序总是有效的，我们需要使用更加数学化的方法。算法分析的两大重点是证明算法是正确的，以及确定算法使用的资源量 (时间和空间)。1 程序验证程序验证取决于两个主要原则
2020-12-28 19:50:44
144
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人