What’s the idea of divide-and-conquer?

Given a problem set of size N, divide it into a small problem of size N /b, then combine the results of each sub-problem and solve each small problem recursively until the final problem is solved

A > = 1 b > 1. Solution time: T(n)=aT(n/b)+O

Use the divide and conquer method to solve the Convex Hull

Convex hull is defined

You can define it in higher dimensions, and here you add a simpler condition


If any two points have different x coordinates and different y coordinates, and three points are not collinear, the smallest polygon that can contain all points is defined as ConvexHux, short for CH(S), and its boundary is defined as a bidirectional list starting clockwise

Violence to solve the Convex Hull problem

Join any two points, construct an edge, and see if all the points are on one side of the edge, if they are on one side, then it is, otherwise it is not.

There are n points, so the number of edges is zeroAt the same time, to check whether all points are on a certain side, then the total time is

Divide-and-conquer solutions

First sort all the points according to the x-coordinate, which takes O(NLGN), select A point x, divide all the points into two parts :CH(A) and CH(B), solve CH(A) and CH(B) respectively, and then merge C(A) and CH(B).

How to merge

The same thing can be done roughly, by looking at all the vertices of the two CH’s, and seeing if all the points are on one side of it. Note: finding the largest y coordinate on both sides as an edge can be problematic

Let’s take the upper boundary for example, and make a straight line for convenience so that it just cuts through the two CH’s, the point that connects the two CH’s., the distance between the axes x selected by these two points is the closest in the two graphs. It intersects the selected axis at the point where the blue line intersects the selected solid axis.






 i=1
 j=1
 while (y(i, j + 1) > y(i, j) or y(i − 1, j) > y(i, j))
     if(y(I, j + 1) > y(I, j)) // Move right clockwise j = j + 1(mod qelseI = I − 1(mod P) // Move left anti-- clockwise p nodesreturn (ai, bj ) as upper tangent
Copy the code

p+q=n

It can be seen that n points are traversed at most in this way, and the time is O(n). The time of the whole process is as follows:


How do I delete unwanted links after merging?

Select the new upper connectionSo, similar lower boundaryAlong the, in a clockwise direction, touching the edge.The point is right on the lower boundary, and then it goes along the lower boundaryContinue clockwise, yesThat’s the merged boundary

Use divide-and-conquer to find the middle value of the numeric size of all elements in an array

The obvious way to do this is sort it, and then you get it directly, and the sorting algorithm takes order NLGN. If you use divide-and-conquer, you can get to O(n). Here’s the idea.

Select (S, I) / / I was to find the elements of a Pick x ∈ S / / Select an element Compute k = rank (x) / / find a place in the queue B = {x ∈ S | y y < x} C = {x ∈ S | y > y}if k = i
     returnThe order of x //x is exactly the same as that of the search positionelse if k>i
     return Select(B, i) 
 else if k<i
    returnSelect (C, I - k)Copy the code

So for x, if you make a bad choice, if there are n of them, and you pick the NTH minus one, and then the NTH minus two, and so on, n over 2 times, and each time you pick the original set of numbers is also O(n), then if you make a bad choice of x the whole time is zero.

What if I take the value of x?

You divide S into five columns, so it’s a two-dimensional array with five rows of data, and you sort each column, and the largest element is at the top, and then x is the middle of all the middle columns

So it’s easy to swap rows and columns

So if you divide it this way, you can see that

  • The number of value elements less than X is at least: 3(n/10-2)
  • The number of value elements greater than X is at least: 3(n/10-2)

I’m going to take the upper bound of n over 10. You can see that there are n over 5 rows, and half of the rows will have numbers less than X, 3 per row, except for the row that contains X and the last row that has less than 5 elements

The total time can be obtained as


All divisions are rounded

T(n/5) is how long it takes to find the middle element in all rows; T(7n/10+6) represents the time required for iteration. After each execution, the remaining number of machines is n-3(n/10-6). O(n) is how long it takes to sort all the columns, there’s only 5 elements in one column, so it’s constant time, there’s n over 5 columns and all of that is O(n).

For the iteration part there are

T(n)<cn/5+c+cn7/10+6c+O(n)
    <cn+7c+an-cn/10
Copy the code

If 7 c + the an – cn / 10 < = 0

70C +10an-cn<=0 c>= 70C /n+ 10A When n>=140, c>=c/2+ 10A, that is, C >=20a, is trueCopy the code

If T(n)<cn, the total time is O(n).