数据结构的复杂度分析

复杂度

• 时间复杂度
  • • 探究算法在时间维度上所消耗资源的核心途径：
    • 空间复杂度

时间复杂度分析

在算法分析中，基本操作重复执行的次数可以通过某个关于n的函数f(n)进行描述，因此算法的时间复杂度可表示为T(n) = O(f(n))。这表明，当问题规模n逐渐增大时，算法运行时间的增长趋势与函数f(n)的增长趋势保持一致，该特性被称为算法的渐进时间复杂度，通常简称为时间复杂度。

若函数f(n)=amnm+am-1nm-1+…+a1n+a0为一个多项式形式，则其对应的时间复杂度可简化为T(n)=O(nm)。 在对算法进行复杂度计算时，可以将所有低阶项以及最高次幂的系数忽略不计，从而实现对算法性能分析的简化处理。

分析算法时间复杂度的基本方法：

• 确定所有语句中出现频率最高的语句，将其视为基础语句；
  • 通过计算基础语句的出现次数，得出问题规模n对应的函数f(n)；
  • 提取其数量级，并使用符号“O”进行表示。

在评估算法的时间复杂度时，主要关注的是随着问题规模n的增大，其增长率的表现。因此，在某些情况下，无需精确计算基本操作的具体执行次数，只需确定其关于n的增长率（即阶数）即可。

例：
for (i=2; i<=n; ++i)
for(j=2; j<=i-1; ++j) { ++