Divide and Conquer algorithms – Why not split in more parts than two?

In divide and conquer algorithms such as quicksort and mergesort, the input is usually (at least in introductory texts) split in two, and the two smaller data sets are then dealt with recursively. It does make sense to me that this makes it faster to solve a problem if the two halves takes less than half the work of dealing with the whole data set. But why not split the data set in three parts? Four? n?

I guess the work of splitting the data in many, many sub sets makes it not worth it, but I am lacking the intuition to see that one should stop at two sub sets.

I have also seen many references to 3-way quicksort. When is this faster? What is used in practice?

It does make sense to me that this makes it faster to solve a problem if the two halves takes less than half the work of dealing with the whole data set.

That is not the essence of divide-and-conquer algorithms. Usually the point is that the algorithms cannot “deal with the whole data set” at all. Instead, it is divided into pieces that are trivial to solve (like sorting two numbers), then those are solved trivially and the results recombined in a way that yields a solution for the full data set.

But why not split the data set in three parts? Four? n?

Mainly because splitting it into more than two parts and recombining more than two results
results in a more complex implementation but doesn’t change the fundamental (Big O) characteristic of the algorithm – the difference is a constant factor, and may result in a slowdown if the division and recombination of more than 2 subsets creates additional overhead.

For example, if you do a 3-way merge sort, then in the recombination phase you now have to find the biggest of 3 elements for every element, which requires 2 comparisons instead of 1, so you’ll do twice as many comparisons overall. In exchange, you reduce the recursion depth by a factor of ln(2)/ln(3) == 0.63, so you have 37% fewer swaps, but 2*0.63 == 26% more comparisons (and memory accesses). Whether that is good or bad depends on which is more expensive in your hardware.

I have also seen many references to 3-way quicksort. When is this faster?

Apparently a dual pivot variant of quicksort can be proven to require the same number of comparisons but on average 20% fewer swaps, so it’s a net gain.

What is used in practice?

These days hardly anyone programs their own sorting algorithms anymore; they use one provided by a library. For example, the Java 7 API actually uses the dual-pivot quicksort.

People who actually do program their own sorting algorithm for some reason will tend to stick to the simple 2-way variant because less potential for errors beats 20% better performance most of the time. Remember: by far the most important performance improvement is when the code goes from “not working” to “working”.

Asymptotically speaking, it doesn’t matter. For example, binary search makes approximately log₂ n comparisons, and ternary search makes approximately log₃ n comparisons. If you know your logarithms, you know that log_a x = log_b x/log_b a, so binary search only makes about 1/log₃ 2 ≈ 1.5 times as many comparisons as ternary search. This is also the reason nobody ever specifies the base of the logarithm in big Oh notation: It’s always a constant factor away from the logarithm in a given base, no matter what the base actual is. So splitting the problem into more subsets doesn’t improve time complexity and practically isn’t enough to outweigh the more complex logic. In fact, that complexity may affect practical performance negatively, increasing cache pressure or making micro-optimizations less infeasible.

On the other hand, some tree-ish data structure do use a high branching factor (much bigger than 3, often 32 or more), though usually for other reasons. It improves utilization of the memory hierarchy: data structures stored in RAM make better use of the cache, data structures stored on disk require fewer reads HDD->RAM.

There are search/sort algorithms that subdivide not by two, but by N.

A simple example is search by hash coding, which takes O(1) time.

If the hash function is order-preserving, it can be used to make an O(N) sort algorithm.
(You can think of any sort algorithm as just doing N searches for where a number should go in the result.)

The fundamental issue is, when a program examines some data and then enters some following states, how many following states are there, and how close to equal are their probabilities?

When a computer does a comparison of two numbers, say, and then either jumps or not, if both paths are equally likely, the program counter “knows” one more bit of information on each path, so on average it has “learned” one bit.
If a problem requires that M bits be learned, then using binary decisions it can’t get the answer in fewer than M decisions.
So, for example, looking up a number in a sorted table of size 1024 can’t be done in fewer that 10 binary decisions, if only because any fewer would not have enough outcomes, but it can certainly be done in more than that.

When a computer takes one number and transforms it into an index into an array, it “learns” up to log base 2 of the number of elements in the array, and it does it in constant time. For example, if there is a jump table of 1024 entries, all more or less equally likely, then jumping through that table “learns” 10 bits. That’s the fundamental trick behind hash coding. A sorting example of this is how you can sort a deck of cards. Have 52 bins, one for each card. Fling each card into its bin, and then scoop them all up. No subdividing required.

Since this is a question about general divide and conquer, not just sorting, I’m surprised no one has brought up the Master Theorem

In brief, the running time of divide and conquer algorithms is determined by two counterveiling forces: the benefit you get from turning bigger problems into small problems, and the price you pay in having to solve more problems. Depending on the details of the algorithm it may or may not pay to split a problem into more than two pieces. If you divide into the same number of subproblems at each step, and you know the time complexity of combining the results at each step, the Master Theorem will tell you the time complexity of the overall algorithm.

The Karatsuba algorithm for multiplication uses a 3-way divide and conquer to achieve a running time of O(3 n^log_2 3) which beats the O(n^2) for the ordinary multiplication algorithm (n is the number of digits in the numbers).

Because of its binary nature a computer is very efficient at dividing things in 2 and not so much in 3.
You get a division in 3 by dividing in 2 first and then divide one of the parts again in 2.
So if you need to divide by 2 to get your 3 division, you might as well divide in 2.

Filed under: softwareengineering - @ 09:50

Thẻ: algorithm-analysis, algorithms

Thiết kế website giá rẻ

Danh mục

Divide and Conquer algorithms – Why not split in more parts than two?