DnC Strategy
Last updated
Was this helpful?
Last updated
Was this helpful?
In the section of Divide-and-Conquer overview, three steps in DnC procedures are discussed. Here in this module, more in-depth discussions will be covered in order to wrap up DnC topic.
Although the high-level idea of DnC is essential in resolving many computation problems, it is worth noted that intuitively meaningful algorithm abstraction in DnC pattern in some scenarios are yet worse than the common way methods. (e.g. simply apply DnC in does not help improve running time but make it more complex to comprehend.)
In general, the DnC problems are large enough to be divided into sub-problems defines a recursive-base, when the sub-problems are small enough to stop recursive calls, a base-case is defined.
Recurrence relations are a series of equations or inequalities to describe functions in terms of its smaller inputs. Solving the recurrence relations will be the key to unravel the computation complexity of DnC problems.
There are three ways to approach recurrence relations:
substitution method, a bound is guess and proven by mathematical induction.
recursion-tree method, recurrences are interpreted as a tree and solved by bounding summations.
, a mathematical generalized form is given for most of the recurrences, and the most important idea to cover than the other two.
Note: is only effective when the original problem gets split into sub-problems with equal size. If sub-problems differ in size, the recursion-method should be used instead.
There are many divide-and-conquer paradigms in a vast amount of computation tasks. DnC principle is helpful yet imperfect to provide a best algorithm pattern at all-time.
As a widely adopted algorithm across various application systems, is simple to evaluate given its identity of a divide-and-conquer algorithm.
For many beginners of divide-and-conquer paradigm, is a good start.
The general idea is to recursively compute the similarities of two arrays from index і to index ј accordingly against the left n/2 (і,ј < n/2) of them and the right n/2 (і,ј > n/2) of them. Upon completion of subroutines above, compute the similarities against the whole length (і < n/2 < ј) and sum all the returned results.
A pair of keys with random arrangement got compared with the in-order keys to output the number of inversions between the two, called the task of . Mathematically speaking, more the difference value between two arrays, more lower the ranking comparisons. It is a widely used algorithm across various subjects such as , etc.
A novel method magically improves the matrix multiplication by adoption of DnC pattern. It counters the method which fails to decrease the running time on average.
Though choosing a pivot in each sub-problem is the major task in algorithm, it utilizes divide-and-conquer in resolving sorting in partitions created in each run.
Its running time Ο(n ⋅ log(n)) maintains the comparison-based sorting lower bound and Quick Sort is a good beginning for randomization techniques.