I am a swifter

当你开始跑步,你就和别人不一样。


swift实现一个时间复杂度为0(N)的斐波那契数列

斐波那契数的定义(摘自维基百科)

费波那契数列(意大利语:Successione di Fibonacci),又译费波拿契数、斐波那契数列、费氏数列、黄金分割数列。

在数学上,费波那契数列是以递归的方法来定义:
F(0) = 0
F(1) = 1
F(N) = F(N-1) + F(N-2)

用文字来说,就是费波那契数列由0和1开始,之后的费波那契系数就由之前的两数相加。首几个费波那契系数是[1]:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

特别指出:0不是第一项,而是第零项。

递归实现斐波那契数列

func fib(n:Int) -> Int
{
    if n<2
    {
        return n
    }
    
    return fib(n-2) + fib(n-1)
}

要计算第n个斐波那契数,需要计算出第n-1和第n-2个斐波那契数。而计算第n-1个斐波那契数的时候又要计算第n-2和n-3个。

		         fib(n)
		        /      \
	    fib(n-1)	    fib(n-2)
        /    \         /     \
fib(n-2)  fib(n-3) fib(n-3) fib(n-4)
  

使用递归的算法计算了大量重复的节点,而且重复的节点随着n的增大急剧增加。计算一个新的fib(n+1)会将已经算好的fib(n)重新计算一次。效率非常低。这个算法的时间复杂度是O(1.6ⁿ)。

可以看到计算fib(20)执行了10946+10945次,速度非常慢,计算fib(30)我已经没有耐心等结果了。那么,怎么来优化呢?

使用字典或数组来实现

优化,首先想到的就是避免重复的计算。我们可以使用字典或者数组来保存已经算好的值。从小到大计算。看了代码就很容易理解了。

字典

func fibDict(n: Int)->Int
{
    var dict = [Int:Int]()
    dict[0] = 0
    dict[1] = 1
    for n in 2...n
    {
        dict[n] = dict[n-1]! + dict[n-2]!
    }
    return dict[n]!
}

数组


func fibArr(n: Int)->Int
{
    var result = [Int]()
    result.append(0)
    result.append(1)
    for i in 2...n
    {
        result.append(result[i-1]+result[i-2])
    }
    return result[n]

}

这个算法的时间复杂度为0(N)。

计算fib(50)只需要执行49次。无需等待,爽。

最近的文章

leetcode Two Sum问题

Two Sum问题是leetcode上面的的第一题,题目是这样的:Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution.Example:Given nums = [2, 7, 11, 15], target = ...…

继续阅读
更早的文章

Hello World

博客终于搭建好了非常感谢 喵神,制作并开源这么好看的博客主题。让我这种小白可以直接使用,真是太感谢了。开始写博客现在开始,写博客。记录学习和成长,帮助沉淀和积累。…

继续阅读