1, the concept:
1?? Algorithm: algorithm is to solve a specific problem or process, strictly, a sequence of instructions that meet the following properties,
Input: have zero or more external quantity as input of the algorithm,
Output: algorithm to produce at least one as well as the output,
Certainty: composition algorithm of each instruction is clear, unambiguous,
Limitation: algorithm in each instruction execution times is limited, the implementation of each instruction time also limited
2?? Application: it is algorithm in some programming language implementation
3?? Data structure: the existence of one or more specific relationship between each other a collection of data elements, the relationship between the data elements called structure
4?? Data types: a set of values and define a set of operations on the value set
5?? The complexity of the algorithm
Time complexity: T=T (N, I)
Space complexity: S=S (N, I)
Three of the time complexity of
Gradual expression, mark O upper and lower bounds of the gradual, progressive world mark Θ
2, the asymptotic order of
Chapter 2 recursive and divide and conquer strategy
1?? Divide and conquer method the basic idea of
Will be a problem of size n is decomposed into k smaller sub-problems, these sub-problems independent from each other and the same as the original problem, recursively solutions for these problems, and then the solution of each sub-problem can be combined to get the original problem's solution,
2?? Partition mode in each layer of the three steps on the recursive
Decomposition, the original problem is decomposed into a series of subproblems;
Solution: recursively solving each subproblems, if the subproblem is small enough, the direct solution;
Merger: will be the result of the subproblems merged into solution of original problem,
3. Divide and conquer method can solve the problems generally has four characteristics of the
1?? The problem of reduced to a certain extent can be solved easily;
2?? This problem can be broken down into several smaller same problem, that is, the problem is in the nature of optimal substructure
3?? By using the solution of problem into sub-problems can be combined for the solution of the problem;
4?? Decomposition of the problem each subproblem is independent of each other, between the subproblems do not include public subproblems,
4, binary search technology (binary search)
The worst time complexity is O (logn)
1. Problem description: n elements of a given already sorted a [0: n - 1), a sequence in which to find a specific element x,
2. The basic ideas of
The typical example of binary search method is to use divide and conquer strategy
1?? Search can easily find reduced to a certain extent;
2?? On a small scale search is the same problem of smaller;
3?? Decomposition of the subproblems can be combined for the solution of original problem;
4?? Decomposition of each sub-problem is independent of each other,
Algorithm description ppt50, algorithm implementation details ppt50, time complexity ppt50, a given example analysis according to the ideas of the algorithm solving process ppt48)
A public static int binarySearch (int [], int x, int n)
{
//in a [0] <=a [1] <=... <=a search] [n - 1 x
//find x returns to its position in the array, otherwise return 1
Int left=0; Int right=n - 1;
While (left & lt;={right)
Int middle=(left + right)/2;
If (x==a (middle)) return middle;
If (x & gt; A [middle]) left=middle + 1;
The else right=middle - 1;
}
return -1;//not found x
}
The algorithm complexity analysis:
Each performs a while loop, cut in half the size of the array to search, therefore, in the worst cases, while loop was carried out O (logn) time, loop operation in our body need to be O (1) time, so the algorithm in the worst case of computing time complexity is O (logn),
5, large integer multiplication problem (lower time complexity thinking: in order to reduce the time complexity, must reduce the number of multiplication) time complexity is O (n2),
6, Strassen matrix multiplication (lower time complexity thinking: in order to reduce the time complexity, must reduce the number of multiplication of matrix multiplication time complexity is O (n3),
7, quick sort,
1?? Basic idea: a visit to the process of quick sort: choose an element as a pivot (or support) (pivot), put all less than its elements in its place, all is greater than its elements in its later,
To pivot on both sides of the subsequence recursively for quick sort, until the order is complete,
2?? Algorithm description
Public static int Partition (int a [], int low, int high) {
Int left, right, pivotkey;
Left=low;
Right=high;
Pivotkey=a, [low].//to take the first element is pivot
While (left
While (left
Left++;
}
//in the left end of the scanning array
While (left
Right -;
}
}
A [left]=pivotkey;
Return the left;
}
Public static void QuickSort (int a [], int low,
Int high)
{
Int pivotLoc:
If (low
PivotLoc=Partition (a, low, high);
QuickSort (a, low, pivotLoc - 1);
QuickSort (a, pivotLoc + 1, high);
}
}
3?? Quick sort performance mainly depends on the partition of symmetry, so the improved algorithm in Patition is the key,
4??
Quick sort of performance improvement ideas
The division of three middle value method applied in either case is better ppt88)
All three of the dividing method of intermediate value
Through from the first, last and middle of the three elements of intermediate value method to select the pivot element,
Easy operation, low cost, divided into
Or similar to that for sequenced sorted sequence, is a good strategy,
The time complexity is O (nlogn),
8, the closest point to the problem (one dimensional space is the closest point to the problem, problem description)
The closest point on the plane to the question:
Given n point on the plane, looking for a pair of these points, made in the n points of all point to point to the smallest distance
