歡迎光臨
每天分享高質量文章

求斐波那契數列第n位的幾種實現方式及性能對比

在每一種編程語言里,斐波那契數列的計算方式都是一個經典的話題。它可能有很多種計算方式,例如:遞迴、迭代、數學公式。哪種演算法最容易理解,哪種演算法是性能最好的呢?

這裡給大家分享一下我對它的研究和總結:下麵是幾種常見的代碼實現方式,以及各自的優缺點、性能對比。

Iteration

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

public class Program
{
    public static void Main()
    {
        var watch = new Stopwatch();
        watch.Start();
        var r = Fibonacci().Take(40).Last();
        watch.Stop();
        Console.WriteLine($"計算結果:{r},耗時:{watch.Elapsed}");
        Console.ReadLine();
    }

    private static IEnumerable<int> Fibonacci()
    {
        int current = 1, next = 1;
        while (true)
        {
            yield return current;
            next = current + (current = next);
        }
    }
}

計算結果:102334155,耗時:00:00:00.0029930

Recursion

using System;
using System.Diagnostics;

public class Program
{
    public static void Main()
    {
        var watch = new Stopwatch();
        watch.Start();
        Func<int, int> fib = null;
        fib = x => x < 2 ? x : fib(x - 1) + fib(x - 2);
        var r = fib(40);
        watch.Stop();
        Console.WriteLine($"計算結果:{r},耗時:{watch.Elapsed}");
        Console.ReadLine();
    }
}

計算結果:102334155,耗時:00:00:00.7022325

Tail Recursion

using System;
using System.Diagnostics;
using System.Threading;

public class Program
{
    public static void Main()
    {
        var watch = new Stopwatch();
        watch.Start();
        Func<int, int, int, int> fib = null;
        fib = (n, a, b) => n == 0 ? a : fib(n - 1, b, a + b);
        var r = fib(40, 0, 1);
        watch.Stop();
        Console.WriteLine($"計算結果:{r},耗時:{watch.Elapsed}");
        Console.ReadLine();
    }
}

計算結果:102334155,耗時:00:00:00.0001280


這幾種實現方式總結:

  • 迭代

代碼邏輯清晰,容易理解,性能中等。

  • 遞迴

代碼最為簡潔,邏輯最清晰,最容易理解,性能最差。

  • 尾遞迴

性能最好,代碼邏輯稍微複雜。

由此可見,不同的演算法對程式的性能影響是十分巨大的,甚至是上千倍以上的差距。

赞(0)

分享創造快樂