二分查找O(logn)和归并排序O(nlogn)时间复杂度介绍 |
您所在的位置:网站首页 › logn与n¾复杂度比较 › 二分查找O(logn)和归并排序O(nlogn)时间复杂度介绍 |
概述
本文通过二分查找和归并排序为例,主要介绍时间O(logn)和O(nlogn)这两个时间复杂度是怎么得出来的。O(1)、O(n)、O(n2)在此不做介绍了,O(n)、O(n2)就是for循环一次、二次,O(1)的话…就好像单例模式或者map吧。 首先,简单看下常见的时间复杂度量级,有个基本的概念。 常数阶O(1)线性阶O(n)平方阶O(n²)对数阶O(logn)线性对数阶O(nlogn)![]() 通常情况下二分查找针对的是一个有序的数据集合进行查找。 他的步骤是将一个规模为N的数据先分为N/2进行比对,再分为N/4、N/8、N/16…直到最后的堆数为1。 假设这个有序数据集的大小为N,将其通过表格的形式进行展示: 次数每堆数量1N/22N/43N/84N/16XN/(2^X)根据表格可以看出,假设执行X次后,堆数为1,即完成了查找。 因此,N/(2^X) = 1。 求出 X = logN 通过X次完成查找,X就代表了二分查找法的时间复杂度------O(logn)。 O(nlogn):归并排序的时间复杂度有了二分查找法的概念,再来看归并排序。此时,假设我们有一个数据量为N的无序数据集。这里提供使用递归和非递归两种方式进行讲解。 1.通过使用递归的方式实现排序递归X次,将N个数划分成2^ X个区间,每个区间的数量为N/(2^X)个 递归次数划分区间每个区间的数量12N/224N/438N/8416N/16X2^XN/(2^X)跟二分查找一样,我们最终要将每个区间的数量变为1。 即递归logN次,将N个数划分为N个区间,每个区间的数量为1。记住这个logN。 当区间长度为1时,进行归并排序的merge操作:从最底层开始(logN层),对相邻两个区间进行合并(利用合并算法进行合并,这里不讨论这个)。 接来下,找下规律: 第logN层,每个区间的数量为1,需要合并对次数为N/2。但N个数字都会被遍历一次,所以这一层的时间复杂度为O(N)。 第2层,需合并的次数为N/4,相邻区间需要合并的次数为2。但这层N个数字会被遍历一遍,所以这一层的时间复杂度也为O(N)。 第1层,需合并的次数为N/2,相邻区间需要合并的次数为1。同样这层N个数字会被遍历一遍,所以这一层的时间复杂度也为O(N)。 那么,每一层的时间复杂度都为O(N),一共有logN层。由此得出,归并排序的时间复杂度时O(nlogn)。 2.通过非递归的方式实现排序非递归的思想与递归的思想基本相同。 首先,将数量为N的数据集分成N个。 第一次merge操作,对1个数字进行合并。 第二次merge操作,对2个数字进行合并。 第三次merge操作,对4个数字进行合并。 …… 直到对所有数字(即对无序数据集的大小个数字进行合并)进行merge操作,就完成了对改无序数据集的排序。 和递归方式相同,每次操作都对N个数字进行了操作,每次时间复杂度都是O(N)。 不难得出,一共需要进行logN次操作,才能完成该大小为N的无序数据集的排序。 因此,用非递归的方式实现归并排序,时间复杂度依然为O(nlogn)。 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |