《计算机算法教程》习题详解：分数分解与时间复杂度计算

《计算机常用算法及程序设计案例教程》是一本面向初学者和进阶者的教材，旨在帮助读者理解和应用各种常见的计算机算法以及掌握程序设计的基本技巧。该教程中的习题涵盖了算法设计、数据结构、时间复杂度分析等多个关键领域。 习题1主要涉及分数分解算法，该算法用于将真分数a/b表示为多个埃及分数（分子为1，分母为整数的分数）的和。算法流程如下： 1. **埃及分数分解**：首先，寻找小于a/b的最大埃及分数1/c，如果c大于900,000,000则终止算法。 2. **迭代更新**：当c在允许范围内时，计算a/b减去1/c的差值，并将其转化为新的分数形式。如果得到的新分数是埃及分数，则输出并结束；否则，重复步骤1-3。 3. **循环结构**：算法通过while循环实现，其中c的值逐步增大，直到满足条件或达到上限。 习题1-2关注的是程序段的时间复杂度分析。具体如下： - （1）两层for循环嵌套，内层循环的次数与外层循环有关，总和为n(n+1)/2，所以时间复杂度为O(n^2)。 - （2）同样为两层循环，但根据n的奇偶性，执行频数不同。当n为奇数时，总频数为(n-1)(n+1)/4；当n为偶数时，总频数为n^2/4。因此，时间复杂度仍为O(n^2)。 - （3）这个循环中，外层计算阶乘的增长速度，内层循环执行次数与阶乘相关，导致时间复杂度为O((n+1)!). - （4）最后的代码涉及三层循环，分别处理每一位数字，对于每个数字，有两次嵌套循环。时间复杂度与n（最大数的位数）成线性关系，但由于内层循环有平方根限制，实际复杂度较难精确量化，但不会低于O(n^2)。 这些习题着重训练了读者对算法设计的理解、循环结构的运用以及算法效率分析的能力，有助于提高编程实践中的问题解决和优化技巧。通过解决这些问题，学习者可以深入理解如何在实际编程中实现高效算法，以及如何通过时间复杂度来评估算法的性能。