算法:分而治之和时间复杂度O(nlogn)如何联系？
And*_*bey 15 algorithm performance big-o divide-and-conquer
在我的算法与数据结构类第一divide-and-conquer algorithm,即merge sort进行了介绍.
在为分配实现算法时,我想到了一些问题.
使用除法和征服范式实现的算法是否具有O(nlogn)的时间复杂度？
是否该方法中的递归部分能够压缩以O(n ^ 2)到O(nlogn)运行的算法？
是什么让这种算法首先在O(nlogn)中运行.
对于(3)我假设这与递归树和可能的递归数量有关.有人可能会用一个简单的分而治之算法来运行,该算法在O(nlogn)中运行如何实际计算复杂度？
干杯,安德鲁
Jav*_*ano 13
我认为你的问题的所有答案都可能来自大师定理它有点告诉你几乎任何分而治之的解决方案你的复杂性是什么,是的,它必须用递归树做一切,通过玩参数你会发现一些分而治之的解决方案不会有O(nlogn)复杂性,实际上有分而治之的算法具有O(n)复杂性.
关于问题2,实际上不可能总是存在一些被认为不可能比O(n ^ 2)更快解决的问题,它依赖于问题的本质.
在O(nlogn)上运行,我认为有一个非常简单的,明确的和教育的运行时间分析算法的一个例子是归并.可以从以下图片中了解:
所以每个递归步骤将输入分成两部分,然后征服部分采用O(n),因此树的每个级别花费O(n),棘手的部分可能是如何递归级别的数量(树高)是登录.这或多或少都很简单.因此,在每个步骤中,我们将输入分成2个n/2个元素,然后递归重复,直到我们有一些恒定大小的输入.所以在第一级我们将n/2除以下一个n/4,然后是n/8,直到我们达到一个恒定大小的输入,它将是树的叶子,以及最后一个递归步骤.
所以在第i个递归步骤,我们除了n/2 ^ i,所以让我们在最后一步找到i的值.我们需要n/2 ^ i = O(1),这是在2 ^ i = cn时实现的,对于某些常数c,所以我们从两边取基数2的对数并得到i = clogn.因此,最后一个递归步骤将是clogn-th步骤,因此树具有clogn高度.
因此,对于每个clogn递归(树)级别,MergeSort的总成本将是cn,这给出了O(nlogn)复杂度.
一般来说,只要递归步骤具有O(n)复杂度,并且yo分解为大小为n/b的b问题,或者甚至更一般,如果部分,您可以确信您的算法将具有O(nlogn)复杂度.是n的线性分数,加起来为n.在不同的情况下,您很可能会有不同的运行时.
回到问题2,在QuickSort的情况下,可能正好从O(n ^ 2)到\ Theta(nlogn),因为平均随机情况实现了一个很好的分区,尽管运行时分析比这更复杂.
不,分而治之并不能保证O(nlogn)的表现.这一切都取决于每次递归时问题如何得到简化.
在合并排序算法中,原始问题分为两半.然后对结果执行O(n)操作.这就是O(n ......)的来源.
现在,这两个子操作中的每一个都有自己n的一半,是原始的一半.每次你递归,你再次将问题分成两半.这意味着递归的数量将是log2(n).这就是O(... logn)的来源.
- @Degustaf我只是想以最简单的方式来解释我自己对过程的理解，以便提供一些见识。 (2认同)
使用分而治之范式实现的任何算法是否具有O（nlogn）的时间复杂度？
平均而言，Quicksort和Mergesort的时间复杂度为O（n log（n）），但不一定总是这样。 大O备忘单
方法中的递归部分是否有能力将像O（n ^ 2）这样的算法凝聚为O（nlogn）？
除了满足您的需求之外，还取决于其他因素，例如与每个递归调用有关的输入操作数。
我强烈推荐此视频，在这里您可以了解为什么MergeSort是O（log（n））。
是什么使得这种算法首先在O（nlogn）中运行。
同样，这仅是算法消耗多少时间（相对于输入大小）的指示，因此，说算法的时间复杂度为O（log（n））并不能提供有关该算法的信息。实施时，它只是说当输入开始增加很多时，所用的时间不会成正比地增加，而是需要更多的时间和更多的时间。
