数据结构总结：时间复杂度的求法-循环主体中的变量的判断

王道数据结构总结1 第一章 绪论 1.1 时间复杂度的求法 （一）循环主体中的变量参与循环条件的判断 a) 找出基本操作 在循环主体中，找出与循环条件相关的基本操作。 b) 设基本操作执行次数为 T(n)，根据初始条件和基本操作语句确定变量与次数的关系式 根据初始条件和基本操作语句，确定变量与执行次数 T(n) 的关系式。 c) 带回循环条件，求出 T(n)，确定 O(n) 将变量与执行次数的关系式带回循环条件，求出 T(n) 的值，从而确定时间复杂度 O(n)。 （二）循环主体中的变量与循环条件无关 （1）递归程序 a) 确定递推关系（注意这里确定的是基本操作次数的递推关系） 对于递归程序，要确定基本操作次数的递推关系。 b) 推出递推关系与执行次数的表达式 根据递推关系，推导出执行次数的表达式。 c) 令低级递推关系中的次数为常数（0 或 1），整理式子 对于递推关系中的低级次数，设为常数（0 或 1），整理表达式。 d) 推导出 T(n) 根据整理后的表达式，推导出最终的执行次数 T(n)。 （2）非递归程序 对于非递归程序，可以采用等比数列或等差数列求和的方法来求解时间复杂度。 1.2 实例 以王道单科第8页的综合第二题为例。 1）归类：循环主体中的变量参与循环条件的判断 基本操作：i (注意不是 k 参与循环条件的判断) 初始条件 i=1，执行一次 i 加一，值为 2；执行第二次，i 再加一，值为 3；... 执行 T(n) 次，i 的值为 T(n) + 1。 带回循环变量：i < n-1，终止条件为 i = n-1；即 T(n) + 1 = n-1 推出 T(n) = n-2，所以 T(n) = O(n) 2）归类：循环主体中的变量参与循环条件的判断 基本操作：y=y+1; 将上述实例中的基本操作语句替换为这个基本操作。 根据相同的步骤，可以推导出最终的执行次数 T(n) 和时间复杂度 O(n)。 以上是对王道数据结构第一章绪论中关于时间复杂度的求法进行的总结。时间复杂度是评估算法效率的重要指标，通过找出循环主体中变量与循环条件的关系，我们可以确定基本操作的执行次数，从而确定算法的时间复杂度。通过实例，我们可以更好地理解和应用这些求法。