An algorithm is any well-defined computational procedure that takes some value or a set of values as input, and produces some value or a set of values as output.(一个程序有输入也有输出,并且输出是固定的。)
Analysis of an algorithm is to predict the resources that the algorithm requires. Resources are measured in relation to a model of computation, which is a mathematical abstraction of a computer on which the algorithm is implemented.
常见的resource:
RAM: time and space (traditional computers)
PRAM: parallel running time, number of processors, and read-and-write restrictions
Message Passing Model: communication cost (number of messages), and computational cost
Turing Machine: time and space
重要的概念:
Input size
Running time: The running time of an algorithm on a particular input is the number of primitive operations or steps executed.
Unless otherwise specified, we shall concentrate on finding only the worst case running time.
Order of growth: To simplify the analysis of algorithms, we are interested in the growth rate of the running time, i.e., we only consider the leading term of a time formula.
n^2 in the expression n^2 + 100n + 5000.
分治策略###
Divide-and-Conquer (D&C) Paradigm
Steps:
- Divide A into a number of subproblems with equal size roughly.
- Conquer the subproblems by solving them recursively. For small enough subproblems, solve them directly without dividing them further.
- Combine the solutions of the subproblems into the solution of the original problem.