斐波那契算法的三种解法(swift)

题目：

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N，计算 F(N)。

解法：

// 方案一：利用递归，时间复杂度为O(2^n)
func fib(_ n : Int) -> Int{
    if n <= 1 {
        return n
    }
    return fib(n-2) + fib(n-1)
}

// 方案二：循环，时间复杂度O(n)
func fib(_ n : Int) -> Int{
    if n <= 1 {
        return n
    }

    var first : Int = 0
    var second : Int = 1
    for _ in 1..<n {
        second += first
        first = second - first
    }
    return second;
}

// 方案三：线性代数解法，时间复杂度O(1)
func fib(_ n : Int) -> Int{
    let c : Double = sqrt(5)
    
    return Int((pow((1+c)/2, Double(n)) - pow((1-c)/2, Double(n)))/c)
}