问题描述

求斐波那契数列的第n项，要求时间复杂度O(n)，空间复杂度O(1)。

在数学上，费波那契数列是以递归的方法来定义：

F（0）= 0

F（1）= 1

F（n）= F（n-1）+ F（n-2） （n >= 2）

特别指出：0不是第一项，而是第零项。

递归

递归的方法虽然简明清晰，但是开销太大，效率太低，会有大量的重复计算。

递归的优化版本

优化版本的递归，把每次计算过的值都保存在字典中，避免大量重复计算。但却需要一个额外的辅助字典（空间复杂度O(n)）。

循环

能用递归解决的问题在优化上的思路必然要考虑循环，而且用循环实现，效率高，开销小。

此方法时间复杂度O(n)，空间复杂度O(1)，是最佳的解决方案。

本文章为大师兄原创文章，转载请注明原文出处：

欢迎访问我的个人博客，博客会第一时间整理更新python笔试面试题及python原创技术文章：