在排序算法中，有多种不同的算法可以选择，这些算法的最坏情况运行时间一般是不同的。比如插入排序和归并排序相比，插入排序的运行时间是 θ(n^2) 而归并排序的运行时间是 θ(nlgn)。
那么，θ(n*lgn) 为什么可以表示归并排序的运行时间。首先，我们先来简单解释一下 θ 这个符号代表什么。这个符号是一个渐进记号。设 f(n) 是能够代表代码的运行时间的函数，f(n) = θ(g(n)) 就表示 存在正常连 c1、c2 和 n0 ,使得对于所有的 n>= n0,有 0 <= c1*g(n) <= f(n) <= c2*g(n)。也就是说 f(n) 这个函数与 g(n) 这个函数在增长速度上是相等的。
理解了 theta 的概念后，下面来探讨归并排序的运行时间的问题。这里所说的归并排序是将一组数字一分为二、二分为四、四分为八，假设数组有 32 个元素，最终会将这个数组分为 32 份。当数组中的元素无法再分时，这种情况就是基准情况，程序中需要有相关代码对这种情况进行处理。就这样，我们将一个大问题分为多个小问题进行处理后再整合起来。每次问题分割都会分为上一个问题的二分之一。
所以，该算法的时间描述为 T(n) = 2*T(n/2) + c*n 。这里只讨论 n > 1 时的情况，其中 c 为一个常数。要证明 T(n) = θ(n*lgn)，我们先来假设有一个足够大的输入 n。
图片.png
观察上图，我们在第一层需要 c*n 的时间，同时第一层会分出两个 T(n/2) 。T(n/2) 的运行时间为 c*n/2，所以第二层的运行时间是 c*n。每个 T(n/2) 都会分出两个 T(n/4)，因此第三层为四个 T(n/4) ，运行时间为 4*c*n/4 = c*n。以此类推，直到分为单个元素不能再分，每一层的运行时间都是 c*n。
至于有多少层，因为每层分为上一层元素的二分之一，设 s 为层数，n为元素数量。
n 除以 2^(s-1) 等于 1，n = 2^(s - 1)，s - 1 = lgn，s = lgn + 1。总时间为 c*n*s，
即 c*n*lgn + c*n。因为增长量级需要忽略系数以及低阶项，所以 T(n) = c*n*lgn + c*n = θ(n*lgn)。
网友评论