算法 之 分治 - 合并排序-小结

之前我们看过的算法 BottomUpSort 和 MergeSort，前者是迭代的，而后者是递归的。

在这里我们可以思考一下，既然能够利用算法 BottomUpSort，为什么还要借助于像 MergeSort 那样的递归算法呢？尤其是考虑到因使用栈而需要的额外空间数，以及由处理递归调用内在开销带来的额外空间。

而且从实践的观点来看，似乎没有理由赞成用递归算法替代其等价的迭代算法。

但是从理论的观点来看，递归算法具有对问题易于叙述、领会和分析等优点。为了理解这一点，我们可以对算法 MergeSort 和 BottomUpSort 的代码作比较，很明显后者需要花更多的时间调试和理解代码的含义。这启示我们设计算法可以从递归描述的框架着手，如果可能，以后再将算法改进并转化为一个迭代的算法。

每个递归算法总是可以被转换为迭代算法的，而且两者在解决问题每个实例时他们的功能是完全相同的。

 

点这里查看 ButtomUpSort

点这里查看 MergeSort

最后再用著名的 Fibonacci 序列来稍微比较一下递归和迭代所耗费的时间。

 

在数学上，Fibonacci 序列是用递归来定义的，它的性质如下所示：

F0 = 0

F1 = 1

F2 = 1

F3 = 2

F4 = 3

F5 = 5

.

.

.

Fn = Fn-1 + Fn-2

 

我们可以用 递归 和 迭代 两种方法来求解 Fibonacci(n) 的值，然后非常直观地比较这两种方法所耗费的时间。

以下这两个方法到了 index=140 的时候，会因为计算结果超过 decimal 类型的最大值而抛出异常

namespace ConsoleApplication.Fibonacci
{
    public class Fibonacci
    {
        public static decimal FibonacciRecursion(int index)
        {
            if (index == 0)
                return 0M;
            else if (index == 1)
                return 1M;

            return FibonacciRecursion(index - 1) + FibonacciRecursion(index - 2);
        }

        public static decimal FibonacciIteration(int index)
        {
            if (index == 0)
                return 0M;
            else if (index == 1)
                return 1M;

            decimal x = 0M, y = 1M, sum = 0M;
            int i = 2;
            while (i <= index)
            {
                sum = x + y;
                x = y;
                y = sum;

                i++;
            }

            return sum;
        }
    }
}

 

然后写一串测试代码来感觉一下花费的时间：

namespace ConsoleApplication
{
    public class Program
    {
        static void Main(string[] args)
        {
            try
            {
                for (int i = 0; i < 10000; i++)
                {
                    Console.WriteLine("Fibonacci({0}) = {1}",
                        i, Fibonacci.Fibonacci.FibonacciIteration(i));
                }
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }

            try
            {
                for (int i = 0; i < 10000; i++)
                {
                    Console.WriteLine("Fibonacci({0}) = {1}",
                        i, Fibonacci.Fibonacci.FibonacciRecursion(i));
                }
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }

            Console.ReadKey();
        }
    }
}

 

程序运行截图

 

运行程序时，可以非常直观的察觉到用迭代方法来计算，结果都是瞬间计算出来的，

而递归算得却很慢，特别是当 index=33-35 时，几乎要花掉1秒钟来计算，而且越到后面需要的时间更是成指数增长