分而治之-为什么有效？ [英] Divide and conquer - why does it work?

问题描述

我知道诸如mergesort和quicksort之类的算法都使用分而治之范式，但是我想知道为什么它可以降低时间复杂度...

I know that algorithms like mergesort and quicksort use the divide-and-conquer paradigm, but I'm wondering why does it work in lowering the time complexity...

为什么通常分而治之算法比非分而治之算法更好？

why does usually a "divide and conquer" algorithm work better than a non-divide-and-conquer one?

推荐答案

分而治之的工作原理是有效的，因为数学支持！

Divide and conquer works, because the mathematics supports it!

考虑一些分而治之的算法：

Consider a few divide and conquer algorithms:

1）二进制搜索：该算法每次都会将您的输入空间减少一半。从直觉上很明显，这比线性搜索要好，因为我们会避免查看很多元素。

1) Binary search: This algorithm reduces your input space to half each time. It is intuitively clear that this is better than a linear search, as we would avoid looking at a lot of elements.

但是好多少呢？我们得到重复（注意：这是最坏情况分析的重复）：

But how much better? We get the recurrence (note: this is recurrence for the worst case analysis):

T（n）= T（n / 2）+ O（1）

数学意味着 T（n）= Theta（log n）。因此，这比线性搜索好得多。

Mathematics implies that T(n) = Theta(log n). Thus this is exponentially better than a linear search.

2）合并排序：在这里，我们分为两个（几乎）相等的两半，对两半进行排序，然后将它们合并。为什么这要好于二次方？这是重复发生：

2) Merge Sort: Here we divide into two (almost) equal halves, sort the halves and then merge them. Why should this be better than quadratic? This is recurrence:

T（n）= 2T（n / 2）+ O（n）

可以用数学方法证明（例如，使用主定理） T（n）= Theta（n log n）。因此，T（n）渐近地优于二次方。

It can be mathematically shown (say using Master theorem) that T(n) = Theta(n log n). Thus T(n) is asymptotically better than quadratic.

观察到天真快速排序最终使我们在最坏的情况下也能重现

Observe that the naive quicksort ends up giving us the recurrence for worst case as

T（n）= T（n-1）+ O（n）

从数学上讲是二次方的，在最坏的情况下，它不比冒泡排序好（渐近而言）。但是，我们可以证明，在一般情况下，快速排序为O（n log n）。

which mathematically, comes out to be quadratic, and in the worst case, isn't better than bubble sort (asymptotically speaking). But, we can show that in the average case, quicksort is O(n log n).

3选择算法：这是一个除法一个寻找第k个最大元素的征服算法。

3 Selection Algorithm: This is a divide a conquer algorithm to find the k^th largest element. It is not at all obvious whether this algorithm is better than sorting (or even that it is not quadratic).

但是从数学上讲，它的重现性（同样是最坏的情况）出来了。成为

But mathematically, its recurrence(again worst case) comes out to be

T（n）= T（n / 5）+ T（7n / 10 + 6）+ O（n）

可以从数学上证明 T（n）= O（n）

也许是查看它们的常用方法：

您可以将算法视为树，其中每个子问题都成为当前子树，并且可以用完成的工作量标记节点，然后可以为每个节点累加总工作量。

You can look at algorithms as tree where each sub-problem becomes a sub-tree of the current and the node can be tagged with the amount of work done and then the total work can be added up for each node.

对于二分查找，功为O（1）（只是一个比较），而其中一个子树的功为0，所以总工作量为O （log n）（本质上是一条路径，就像我们在二叉搜索树中所做的一样。）

For binary search, the work is O(1) (just a compare), and one of the sub-trees, the work is 0, so the total amount of work is O(log n) (essentially a path, just like we do in binary search trees).

对于归并排序，对于有k个孩子的节点，工作为O （k）（合并步骤）。每个级别完成的工作为O（n）（n，n / 2 + n / 2，n / 4 + n / 4 + n / 4 + n / 4等），并且存在O（log n）个级别，并且因此，合并排序为O（n log n）。

For merge-sort, for a node with k children, the work is O(k) (merge step). The work done at each level is O(n) (n, n/2 + n/2, n/4 + n/4 + n/4 + n/4 etc) and there are O(log n) levels, and so merge sort is O(n log n).

对于快速排序，在最坏的情况下，二叉树实际上是一个链表，因此完成的工作是n + n- 1 + ... + 1 = Omega（n ^ 2）。

For quicksort, in the worst case the binary tree is actually a linked list, so work done is n+n-1 + ... + 1 = Omega(n^2).

对于选择排序，我不知道如何可视化它，但我相信将其视为一棵有3个孩子（n / 5、7n / 10以及其余）的树可能仍然有帮助。

For selection sort, I have no clue how to visualize it, but I believe looking at it as a tree with 3 children (n/5, 7n/10 and the remaining) might still help.

这篇关于分而治之-为什么有效？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！