斐波那契数列（python实现）

斐波那契数列的形式如下：
f(0)=0,f(1)=1,f(2)=1,当n>=3时，f(n)=f(n-1)+f(n-2)
分析可以发现：n大于等于3时，每次计算都会使用到最近的前面连个元素，如果直接使用递归的方式计算的话，时间复杂度太高，所以这里可以使用一个两元素的列表，用于交替存储每次计算后的结果，最后根据n的奇偶性输出列表中的对应元素即为最终的结果。

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        #if n <= 1:
        #    return n
        #return self.Fibonacci(n-1) + self.Fibonacci(n-2)   #计算复杂度为2^n,太高
        if n <=1:
            return n
        else:
            a = [1,1]
            for i in range(3,n+1):
                if i % 2 != 0:
                    a[0] = a[0] + a[1]
                else:
                    a[1] = a[0] + a[1]
            if n % 2 == 0:
                return a[1]
            else:
                return a[0]

时间复杂度为：O(n)