算法:分治法和时间复杂度O(nlogn)有何关系? [英] algorithms: how do divide-and-conquer and time complexity O(nlogn) relate?

问题描述

在我的算法和数据结构类中，引入了第一个divide-and-conquer algorithm即merge sort.

In my Algorithms and Data Structures class a first divide-and-conquer algorithm namely merge sort was introduced.

在为作业实现算法时，我想到了几个问题.

While implementing an algorithm for an assignment a few questions came to my mind.

1. 使用分而治之范例实现的任何算法是否具有O(nlogn)的时间复杂度?

1. Does any algorithm that is implemented with the use of the divide and conquer paradigm has time complexity of O(nlogn)?

方法中的递归部分是否有能力将运行在O(n ^ 2)中的算法浓缩为O(nlogn)?

Is it that the recursion part in the approach has the power to condense an algorithm that runs in O(n^2) to O(nlogn)?

是什么让这种算法首先在O(nlogn)中运行?

What makes such an algorithm run in O(nlogn) in the first place?

对于(3)，我认为这与递归树和可能的递归次数有关.有人可以用在O(nlogn)中运行的简单分治算法来演示，它是如何实际计算复杂度的吗?

For (3) I assume that this has something to do with recursion trees and the possible number of recursions. Could someone probably show with a simple divide-and-conquer algorithm that runs in O(nlogn), how the complexity is actually computed?

干杯， 安德鲁

推荐答案

我认为，您问题的所有答案都可能来自 divide和征服具有O(n)复杂度的算法.

I think all the answers to your question might come from the Master Theorem It kind of tell you what would be your complexity for almost any divide and conquer solution you have, and yes, it has to do everything with recursion trees, by playing with the parameters you will find that some divide and conquer solutions won't have O(nlogn) complexity, in fact there are divide and conquer algorithms that have O(n) complexity.

仅就问题2而言，不可能总是存在，实际上，有些问题被认为不可能比O(n ^ 2)更快地解决，这取决于问题的性质.

Just regarding question 2, it is not possible always, in fact, there are some problems that are believed to be impossible to solve faster than O(n^2), it dependes on the nature of the problem.

合并排序.可以从以下图片中了解它:

An example of an algorithm that runs in O(nlogn) and that I think has a very simple, clear and educational run time analysis is MergeSort. It can be grasped from the following picture:

因此，将输入的每个递归步骤分为两个部分，然后征服部分取O(n)，因此树的每一级花费O(n)，棘手的部分可能是如何可能递归级别(树高)被登录.那或多或少是简单的.因此，在每个步骤中，我们将输入均分为n/2个元素的2个部分，然后递归重复，直到我们得到一些恒定大小的输入为止.因此，在第一个级别上，我们将n/2除以下一个n/4，然后除以n/8，直到我们得到一个恒定大小的输入(它将是树的叶子)和最后一个递归步骤.

So each recursive step the input is split into two parts, then the conquer part takes O(n), so each level of the tree costs O(n), the tricky part might be how is it possible that the number of recursive levels (tree height) is logn. That is more or less simple. So at each step we divide the input in 2 parts of n/2 elements each, and repeat recursively, until we have some constant size input. So at the first level we divide n/2, on the next n/4, then n/8, until we reach a constant size input that will be a leaf of the tree, and the last recursive step.

因此，在第i个递归步骤中，我们将n/2 ^ i相除，因此让我们在最后一步找到i的值.我们需要n/2 ^ i = O(1)，对于2个常数c，当2 ^ i = cn时可以实现，因此我们从两边取2为底的对数，得到i = clogn.因此，最后的递归步骤将是克隆"步骤，因此树具有克隆高度.

So at the i-th recursive step we divide n/2^i, so lets find the value for i at the last step. We need that n/2^i = O(1), this is achieved when 2^i = cn, for some constant c, so we take the base 2 logarithm from both sides and get that i = clogn. So the last recursive step will be the clogn-th step, and thus the tree has clogn height.

因此，对于每个克隆递归(​​树)级别，MergeSort的总成本将为cn，这会带来O(nlogn)复杂性.

Thus the total cost of MergeSort will be cn for each of the clogn recursive (tree) levels, which gives the O(nlogn) complexity.

通常，您可以确信，只要递归步骤具有O(n)复杂度，您的算法将具有O(nlogn)复杂度，并且可以分解为b个大小为n/b或更普遍的问题，如果零件是n的线性分数，则n等于n.在不同的情况下，您很有可能会有不同的运行时.

In general, you can be confident that your algorithm will have O(nlogn) complexity as long as the recursive step has O(n) complexity, and yo divde into b problems of size n/b, or even more general, if the parts are linear fractions of n which adds up to n. In a different situation it is very likely that you will have a different runtime.

回到问题2，在QuickSort的情况下，可能是因为平均随机情况实现了很好的分区，所以从O(n ^ 2)到\ Theta(nlogn)，尽管运行时分析比这还要复杂.

Returning to question 2, in the case of QuickSort one might get from O(n^2) to \Theta(nlogn) precisely because the average random case achieves a nice partition, though the runtime analysis is even more complex than that.

这篇关于算法:分治法和时间复杂度O(nlogn)有何关系?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！