Shulou(Shulou.com)06/01 Report--

Three methods of analyzing Recursive algorithm

Substitution method, iterative method, general method (master method)

Function: analyze the running time of recursive algorithm

Divide and conquer algorithm

A problem is decomposed into several sub-problems similar to the original problem but smaller in scale, these sub-problems are solved recursively, and then the solutions of these sub-problems are combined to form the solution of the original problem. This method consists of three steps on each level of recursion:

Divide (decomposition): divide the problem into several sub-problems

Conquer (solving): recursively solve these sub-problems; if the Size of the sub-problems is small enough, solve them directly

Combine (combination): combine the solution of a subproblem into the solution of the original problem.

The second step is crucial: recursive call or direct solution (recursive termination condition), and some algorithms are easy to "decompose" and some are easy to "combine".

Examples of divide-and-conquer method:

Merge and sort

① decomposition: dividing n elements to be sorted into two subsequences whose Size is nprime 2

② solution: recursively call merge sort to sort the two subsequences. If the length of the subsequence is 1, it is naturally ordered, and there is no need to do anything (solve it directly).

③ combination: merge these two sorted subsequences into an ordered sequence

Obviously, it is easy to decompose (split into two), but difficult to combine.

Quick sort

Just analyzed, quick sorting is the division of pivot records, that is, it is difficult to decompose, but easy to combine. A [1... ≤ A [k] ≤ A [Kmur1]... N]

Analysis of divide and conquer algorithm

Let T (n) be the execution time where Size is n. If Size is small enough, such as n ≤ C (constant), then the time of direct solution is θ (1).

① sets the time to complete the partition as D (n)

When ② is decomposed, it is divided into a sub-problem, each sub-problem is 1max b of the original problem, then the time of solving each sub-problem is aT (n-prime b).

③ set combination time C (n)

In general, the recursive solution is divided, but the details can be ignored when solving the recursive formula.

① assumes that function arguments are integers, such as

The ② boundary condition can be ignored. When n is small, T (n) = θ (1).

Because these details generally only affect the size of the constant factor, do not change the order of magnitude. When solving, ignore the details first, and then decide whether it is important or not!

Method of analysis

Replacement method

Guess the solution, use mathematical induction to determine the constant C, prove that the solution is correct, the key step is to use the guessed solution into the recursion.

Make a good guess (there is no general way, only based on experience)

If ① is similar to the solution seen before, guess it.

The upper and lower bounds of ② probands are looser, which reduces the scope of guessing.

Detail correction

Sometimes the guess solution is correct, but mathematical induction can not directly prove its details, because mathematical induction is not strong enough to prove its details. In this case, a lower-order term can be subtracted from the guess solution to satisfy the mathematical induction.

Avoid traps

Similar to the mathematical induction of summation, it is easy to make errors in the use of asymptotic symbols in proof.

Variable transformation

Sometimes changing variables can turn unknown recursions into familiar ones. For example:

Iterative method

Expansion: without guessing, expand the recursion to a sum that depends only on n and boundary conditions, and then use the summation method to demarcate it. Need to pay attention:

1. The number of iterations required to reach the boundary condition

2. The sum in the iterative process. If the form of the solution has been estimated in the iterative process, the replacement method can also be used.

3. When the recursion contains floor and ceiling functions, it is often assumed that the parameter n is an integer power to simplify the problem.

Recursive tree

Visualize the deployment process

For example: t (n) = 2T (nAccord 2) + n ^ 2 (you might as well set nhat 2k)

The master method (general method, universal method)

Can be solved quickly.

T (n) = aT (nplink b) + f (n) / / constant a ≥ 1, b > 1, f (n) asymptotically positive

Meaning: the problem with Size n is divided into a sub-problems, and each sub-problem Size is n-prime b. The time of each sub-problem is T (n), and the time of partition and combine is f (n).

Note: nCompare b is not necessarily an integer, it should be ncompanyb or ncompanyb, which will not affect the asymptotic bound.

Understanding and comparison of Recursion and Loop

Recursive popular is a function to call the function itself (itself), this calling process is called recursion, recursion is a double-edged sword (sometimes convenient, sometimes bad). If the new channel IELTS training needs to deal with repeated problems that require multiple calculations, you can usually choose to use recursion or loop, but the execution efficiency of recursion is not as efficient as the loop statement.

Note: conditional detection for terminating recursion must be set, otherwise it is used with caution.

Up_and_down (); up_and_down (, n, & (n)

< + , n, & 首先，main函数用参数1调用递归函数，递归函数形参n=1，打印语句level1……然后，n 12) { printf("输入1-12的整数!"); } else { printf("\n%d的阶乘=%d", num, factorial(num)); printf("\n%d的阶乘=%d", num, loopFactorial(num)); } printf("\n输入1-12的整数"); } system("pause"); return 0;} //循环计算阶乘int factorial(int n){ int temp; for (temp = 1; n >

1; n temp -) {temp * = n;} return temp;}

/ / use recursive calculation of factorial int loopFactorial (int n) {int temp; if (n > 0) {temp = n * loopFactorial (n-1); / / belong to tail recursion, if n > 0, then this is the last sentence} else {temp = 1 bump / there must be a recursive termination condition! } return temp;}

Note: integer range, 32-bit machines, int type up to more than 2.1 billion, then use long long or double type, generally speaking, choose a loop better, recursive each call must have its own set of variables, occupy a large memory, each time to store a new set of variables to the stack, so slow, but recursion (the simplest is tail recursion) is relatively simple. Some situations still need to be used.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.