运行时间
概述
运行时间 是衡量算法效率的基本指标，指算法执行的基本操作次数。它是输入规模的函数，CLRS关注的是运行时间的增长量级而非精确值。
定义
运行时间
算法的运行时间是算法在RAM模型下执行的基本操作次数，通常表示为输入规模 的函数 。对于不同的输入实例，同一算法的运行时间可能不同。
核心性质
- 运行时间依赖于输入规模 和输入本身的内容。
- CLRS通常关注运行时间的上界，即最坏情况或平均情况的运行时间。
- 运行时间的分析通常忽略常数系数和低阶项，关注渐近行为。
- 运行时间可以按情况分类：最好情况（best case）、最坏情况（worst case）、平均情况（average case）。
章节扩展
第2章：入门
- 2.2 算法分析：以插入排序为例，分析其运行时间。分别计算最好情况（输入已有序，）和最坏情况（输入逆序，）下的运行时间，引入增长量级的概念。