为什么 θ(nlgn) 可以表示归并排序的运行时间

作者 : 开心源码 本文共848个字,预计阅读时间需要3分钟 发布时间: 2022-05-12 共147人阅读

在排序算法中,有多种不同的算法可以选择,这些算法的最坏情况运行时间一般是不同的。比方插入排序和归并排序相比,插入排序的运行时间是 θ(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)。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 为什么 θ(nlgn) 可以表示归并排序的运行时间

发表回复