优化整数排序与多项式计算：数据结构实例

本资源是一份关于2016年广州工业大学（广工）AnyView数据结构课程的练习答案文档，主要包括三个部分的算法题解答。以下是详细的知识点解析： 1. 题目一：非递增整数排序算法 - 函数descend() 的目的是通过交换整数a、b和c的值，确保它们满足非递减顺序。当c小于或等于b且b小于或等于a时，函数返回；否则，它会检查三个数的大小关系，通过`swap()`函数进行必要的交换，最终使得a、b和c按照非递增顺序排列。这个算法的时间复杂度为O(3)，因为最多需要执行三次交换操作。 2. 题目二：一元多项式求值算法 - 函数Polynomial() 计算一元多项式P(x) = a0 + a1x + a2x^2 + ... + anx^n的值，给定n、系数数组a和变量x。该函数通过循环，依次计算每一项的乘积并累加到answer中。时间复杂度为O(n)，因为有n次乘法和加法操作。函数中的每一句话执行次数与n成正比。 3. 题目三：k阶斐波那契数列求值算法 - StatusFibonacci() 函数用于求解k阶斐波那契数列的第m项值。数列定义为f(0) = 0, f(1) = 0, ..., f(k-2) = 0, f(k-1) = 1; f(n) = f(n-1) + f(n-2) + ... + f(n-k)。函数首先检查输入参数的合理性，若k小于等于1或m小于0，返回错误。然后，对于m等于k的情况，函数直接返回1（因为f(k) = 1）。对于其他情况，递归计算斐波那契数列，时间复杂度取决于m与k的关系，但因涉及递归调用，最坏情况下可能达到O(2^(k-1))。 这些算法都是基础的编程技巧，它们展示了如何处理数值比较、数组操作以及递归解决问题。在实际编程中，理解和掌握这类算法对于提高代码效率和解决复杂问题至关重要。通过这份答案文档，学习者可以加深对数据结构概念的理解，如数组操作、排序算法和递归，以及如何在实践中优化时间复杂度。