您的位置: 首页 > 文章 > 算法导论lec1算法分析

算法导论lec1算法分析

分类: 文章 • 2024-01-24 18:13:34

算法的理论研究是性能和资源利用。有很多比性能重要的要素，但研究性能还是学习算法原因。
插入排序为例
1.伪代码如下：

2.算法示意图如下：
- 运行时间依赖于输入和输入规模
- 几种运行时间：最坏、平均，其中最坏运行时间又取决于机器速度，分为绝对速度和相对速度
- Big idea：忽略机器时间而依赖常数，不看运行时间而看增长
- 插入最坏运行时间的计算
  $T(n)=\sum_{i=1}^n\Theta(j) =\Theta(n^2)$

归并排序
伪代码如下：
- 重要子程序Merge，合并两个排序数组
  Merge子程序算法示意图如下
- 归并运行时间分析
  - 归并排序的递归表达式为：
  - 递归树求解该递归表达式
    平均运行时间分析如下：