斐波那契数列的时间复杂度分析

斐波那契数列是一个经典的递归问题，其时间复杂度可以通过递归树来分析。假设我们要求第 n 个斐波那契数，那么我们需要计算第 n-1 和第 n-2 个斐波那契数，而计算第 n-1 个斐波那契数又需要计算第 n-2 和第 n-3 个斐波那契数，以此类推。因此，递归树的深度为 n，每个节点需要计算两个子节点，因此递归树的节点总数为 2^n。因此，斐波那契数列的时间复杂度为 O(2^n)。

当然，我们可以通过记忆化搜索或动态规划来优化斐波那契数列的时间复杂度。记忆化搜索的时间复杂度为 O(n)，动态规划的时间复杂度也为 O(n)。