斐波那契序列函数实现及时间、空间复杂度分析

以下是完整的斐波那契序列函数及相关复杂度的分析： ```c int fib (int n) { int a = 1, b = 1, i, s; if (n == 1 || n == 2) return(1); for (i = 3; i <= n; i++) // 从第 3 项开始计算 { s = a + b; // 计算当前项 a = b; b = s; } return b; // 返回第 n 项的值 } ``` 算法的时间复杂度：$O(n)$ 。因为循环执行了 $n - 2$ 次来计算第 $n$ 项的值。 算法的空间复杂度：$O(1)$ 。因为只使用了固定数量的几个整数变量，不随输入规模 $n$ 的增加而增加。 ######[AI写代码神器 | 210点数解答 | 2024-11-14 00:31:43]