数据结构之算法分析

本部分内容旨在使读者对时间与空间复杂度以及算法评估标准形成基本认知，从而为后续学习奠定基础，便于在实际应用中对各类数据结构的运行效率进行科学评估，并实现更直观的对比分析。

一、算法代价

代价可以划分为两类，分别为时间代价与空间代价。

时间代价主要体现为算法在运行过程中所消耗的时间资源。

空间代价则指的是算法在执行时对存储空间的需求量。

在对某一算法进行评估时，应确保其能够客观地反映出该算法本身的运行效率，而不受具体执行时所处的硬件条件或软件环境的影响。

针对算法的评估可以从三个不同的维度展开，包括最差情况、最佳情况以及平均情况。

用于比较不同算法的方式主要包括事后统计法与事前分析估计法。事后统计法的具体操作是选取两个算法进行实际运行，并通过收集相关性能参数来对比它们的资源消耗情况；而事前分析估计法则被称为渐进性算法分析，其核心在于预估当问题规模逐渐扩大时，某一算法可能产生的资源消耗趋势。

二、时间代价

将执行算法所需耗费的时间T表示为输入规模n的函数形式T(n)

典型的时间复杂度类型：

三、渐进分析方法与应用

当输入数据量趋向于无限增大时，对算