Features
Features:

Product Tour >

Edraw AI >

Paid Plans:

Individuals >

Business >

Eduaction >
Resources
Blog

History

How-tos & Tips

Discovery

Biography

Business Analysis

Examples

AI concept Map

Free AI Mind Map Generator

Onenote Mind Map

Bcg Matrix Examples

Nike Marketing Strategy

Unilever SWOT Analysis

Make Mind Maps in Google Docs

Guide

FAQs

What's New

Resource Center
Templates
All Templates

Brain Storming Templates

Strategy and Planning Templates

Project Management Templates

Product Management Templates

Human Resources Templates

Agile Workflow Templates

Marketing Templates

Education Templates

Fun and Games Templates

User Gallery
Download
Pricing
Enterprise

MindMap Gallery Summary of divide-and-conquer recursive algorithm

Summary of divide-and-conquer recursive algorithm

The divide-and-conquer strategy is to divide large problems into small problems and recursively divide them downwards. Each small problem is independent of each other and can be solved independently at the same time. The solution to the original problem is merged from bottom to top. The relevant strategies and algorithms for other specific problems are also briefly introduced.

Edited at 2021-12-28 11:01:24

PlotWizard

Recent works View more works>>

Summary of divide-and-conquer recursive algorithm

PlotWizard

Recent works View more works>>

Recommended to you
Outline

divide and conquer recursion

strategies and methods

divide and conquer strategy

Big problems are divided into small problems, and then recursively divided downwards (the problem types are the same)

Each small problem does not depend on each other and can be solved independently at the same time.

Bottom-up merging to find the solution to the original problem

recursive strategy

Appears during the downward reduction process of re-divide and conquer

two elements

Boundary conditions

recursive equation

Classic question

Arrangement problem

When n=1, perm(R)=(r), where r is the only element in the set R

When n>1, perm(R) is given by (r1)perm(R1), (r2)perm(R2),…, (rn)perm(Rn)

Integer division problem

Add an independent variable: record the number of divisions where the maximum addend n1 is not greater than m as q(n, m), e.g. q(6, 3)

(1) q(n, 1)=1, n1; e.g. 6=1 1 1 1 1 1 //When the maximum addend n1 is not greater than 1, any positive integer n has only one division form, that is, n=1 1 … 1 (2) q(n, m)=q(n,n), mn; e.g. q(6, 7)=q(6, 6) //The maximum addend n1=m actually cannot be greater than n, therefore, q(1,m)=1 (3) !!!p(n)=q(n, n)=1 q(n, n-1) //The second variable in the problem size decreases The division of positive integer n consists of the division of n1=n and the division of n1≤n-1 e.g. q(6, 6) = 1 q(6, 5) (4) q(n, m)=q(n, m-1) q(n-m, m), n>m>1; e.g. n=6, m=4, q(6, 4) = q(6,3) q(2, 4) = q(6,3) q(2, 2)

Tower of Hanoi problem

hanoi(n-1, a, c, b); /*Move n-1 plates on A to C with the help of B move(a,b); /*Move the remaining largest/bottom plate on A directly to B hanoi(n-1, c, b, a); /*Place n-1 plates on C, With the help of A, move to B

Improve

user defined stack

Recursion to implement recursion

Convert to tail recursion

design method

Applicable issues

Optimal substructure properties—the same problem on a smaller scale

The solution to the problem can be merged using the solutions to the decomposed sub-problems. There is no certain dependence between the sub-problems.

If not-----》Dynamic programming or greedy algorithm

Design principles and solution steps

if the scale is small---》Solution

If the scale is large---》Decompose

Pay attention to balance

Solving subproblems recursively

Merge to solve

the complexity

Divide a problem of size n into k sub-problems of size n/m

Total logmn-1 layer

The size of the problem at level j is n/mj

The number of problems at level j is k raised to the jth power

The cost of serial solving

The decomposition and merging costs of each layer are accumulated

Specific issues

binary search

Reduction without recursion

int BinarySearch(Type a[], const Type& x, int l, int r) { while (r >= l){ int mid = (l r)/2; if (x == a[mid]) return mid; if (x < a[mid]) r = mid-1; else l = mid 1; } return -1; }

O(logn)

sort

merge sort

Simple merge sort

step

1. Divide array a into left and right parts

if (left<right) { //*At least 2 elements int i=(left right)/2; //*Get the midpoint

2. Call merge sort on the left and right parts respectively

mergeSort(a, left, i); //*Solve the left sub-problem mergeSort(a, i 1, right); //*Solve the right sub-problem

3. Merge the left and right results into b

merge(a, b, left, i, right); //Merge and copy to array b, key!

0. Set up three pointers, one is the pointer of the target array, and the other two are pointers of the left and right sequential arrays respectively.

int i=l, //The starting point of the search comparison pointer of the left subsection j=m 1, //The starting point of the search comparison pointer of the right subsection k=l;

1. Scan the left and right arrays from left to right at the same time

while (( i<=m) && (j<=r)

2. If the current left pointer is larger, assign the value of the left pointer to the target array pointer, and both move forward. else does the same for the right pointer

if (c[i] <=c[j]) d[k ]=c[i ]; else d[k ]=c[j ];

3. After each move in step 2, check whether the left and right pointers exceed the limit. If so, the rest of the other part of the array that has not exceeded the limit will be placed at the end of the target array.

f (i>m) for (int q=j; q<=r; q ) d[k ]=c[q]; else for (int q=i; q<=m; q ) d[k ]=c[q];

4. Copy array b back to array a

the complexity

Worst time complexity O(nlogn) average time complexity O(nlogn) Auxiliary space: O(n)

Improvement--Non-recursive merge sort

Omit the top-down decomposition process, pair adjacent elements in a[] as the lowest-level sub-problem, and use the merge process from bottom to top to sort.

step

0. Create transit array b

1. Set the initial value of the merged length s = 1

2. When the merged length value is less than n, continue the merge step.

3. Merging twice in one loop solves the problem of copying b back.

MergePass(a, b, s, n);

0. Set the starting position pointer of the arrays at both ends to be merged. The initial value is i=0.

1. When there is no end stage, most of the arrays are merged (i<=n-2*s)

Merge(x, y, i, i s-1, i 2*s-1);

i=i 2*s;

2. The loop jumps out and has come to an end.

If the length of the last part is less than s, copy it directly to the end of the target array.

for (int j=i; j<n-1; j ) y[j]=x[j];

If it is between s and 2s (i s<=n), change the target point of mergr to the tail, and still need to merge

Merge(x, y, i, i s-1, n-1);

s =s;

MergePass(b, a, s, n); //Merge into array a

s =s;

Quick sort

step

0. When there are at least two elements

1. Select a[q] and divide a[] into two left and right parts. The right part is always larger than the left part.

Partition(a,p,r)

0. Select the starting element as the base element x

1. Set up two pointers, i from left to right and j from right to left.

2. Continue exchange when i<j

i searches from left to right to a position larger than the reference x, j searches from right to left to a position smaller than x

while (a[ i] <x && i<r); while (a[- -j] >x);

Swap the elements at these two positions

Swap(a[i], a[j]);

3. Swap the element at position j with the base element

a[p] = a[j]; a[j] = x;

Sort the left half recursively

QuickSort (a,p,q-1);

Sort the right half recursively

QuickSort (a,q 1,r);

Improve

Avoid partitioning of sorted arrays

If it is not decrementing, it will be returned directly.

If non-increasing, return in reverse order.

Randomly select base elements for partitioning

Swap it to the first position after selection so the other steps remain the same

the complexity

Worst time complexity: O(n2)

Average time complexity: Θ(nlgn)

Best time complexity: (nlogn)

Auxiliary space: O(n) or O(logn)

Worst-case time complexity of comparison-based sorting algorithm, asymptotically lower bound is Ω(nlogn)

multiplication

Large integer multiplication

Bit-by-bit multiplication and addition - n2 multiplications, O(n) additions The efficiency is too low

Mainly to reduce the number of multiplications

Method 1, no improvement - XY = ac 2n (bc ad) 2n/2 bd

m=2,k=4

Method 2 - Replace one multiplication with two subtractions and one addition - ac 2n ( (a-b)(d-c) ac bd) 2n/2 bd

m=2,k=3

Strassen matrix multiplication

For 2*2 matrix multiplication, it is converted into 7 multiplications

linear time selection

Given n elements in a linear sequence and an integer k, 1≤k≤n, you are required to find the kth smallest element among these n elements.

step

1. Select the reference element x from the array a, and Partate the array into two parts

Optimization--reduce the worst complexity n-square

0. If the array is small enough, sort it using a simple sorting algorithm

1. Divide the array into 5 subsequences, select the median in each subsequence, and move it to the leftmost end.

for ( int i = 0; i<=(r-p-4)/5; i ) // i represents the 5-long group sequence number { int s=p 5*i; //s is the starting point of the group t=s 4; //t is the end point of the group for (int j=0; j<3; j ) bubble(s, t-j);//After 3 calls, the median has appeared swap(a, p i, s 2); // }

2. In the leftmost median part, call select recursively to select the median as the dividing basis x

Select(a, p, p (r-p-4)/5, (r-p 6)/10);

2. If the length of the left part is less than k, then search a[q 1:n-1] recursively in the right array. Otherwise in the left part, search recursively for a[0:q]

j=i-p 1; //Left subsegment length if (k<=j) return Select(a, p, i, k); else return Select(a, i 1, r, k-j);

Mathematical proof of optimization

x is at least larger than 3n/10-1 elements in a[0: n-1]

reasoning

m=n/5, the medians of m/2-1 groups before the group where x is located are all smaller than x

Each group has a total of 3 elements less than x

For the group where x belongs, there are 2 elements <x

3*(m/2-1) 2=3m/2-1=3n/10-1 elements are less than x

example

It is required that the length of the two subarrays after division is reduced by at least 1/4, n=? When n≥20, (3n/10 -1) ≥ n/4: 40*(3n/10 -1) ≥ 40*(n/4), 12n-40 ≥ 10n, n ≥ 20

the complexity

T(n)=O(n)

Plane nearest point pair

Given a set S of n points on the plane, find a pair of points such that the distance between the pair of points is the smallest among all pairs of n points.

step

0. Sort all points according to x coordinate and find the median as the dividing line

1. Determine the number of points. 1 point means infinity, 2 points means finding the distance between two points, and 3 points means comparing them two by two.

End of recursion sign

2. d1 = the distance between the nearest point pair in the left half of the interval, d2 = the distance between the nearest point pair in the right half of the interval, d = min{ d1, d2 }

closest(X, Z, Y,L,m,a,b,d);

closest(X, Z, Y,m 1,r,ar,br,dr);

if (dr<d) { a=ar; b=br; d=dr}

3. Taking the vertical dividing line of the left and right intervals as the center, include a total of k points with a width of d, and discard the others to form an array Z

for (int i=L; i<=r; i ) if (y[i].x >m) z[g ]=y[i] else z[f ]=y[i];

int k=L; for (int i=L; i<=r; i ) if (fabs(Y[m].x-Y[i].x))<d Z[k ]=Y[i];

4. Sort the array Z according to the y coordinate

merge(Z,Y,L,m,r);

5. Perform a linear scan of the array Z

For point Z[i], scan only points whose y-axis distance is within d and calculate their distance dist(Z[i],Z[j])

for (int i=L; i<=k; i) //Search Z[L:k-1] { for (int j=i 1; j<k&&Z[j].y-Z[i].y <d; j ) { float dp=distance(Z[i],Z[j]); if (dp<d) { d=dp; a=X[Z[i].p], b=X[Z[j].p]; } } }

d = min(d,d3)

round robin problem