第一章算法基础1.pptVIP

算法 常用技术 分治法 （Divide and Conquer） 贪心法 （Greedy） 动态规划法 （Dynamic programming） 回溯法 （Backtracking） 分枝界限法 （Branch and Bound） 线性规划与网络流（Liner Programming and Network Flow） 近似算法 (approximation algorithm） 第1章 算法引论 1.1 算法与程序 Algorithm: a method or a process followed to solve a problem. A recipe. An algorithm takes the input to a problem (function) and transforms it to the output. A mapping of input to output. A problem can have many algorithms. 算法与程序 An algorithm possesses the following properties: 输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 程序:是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。 1.2 表达算法的抽象机制 抽象数据类型 1.3 描述算法 1.4 算法复杂性分析 Algorithm Efficiency There are often many approaches (algorithms) to solve a problem. How do we choose between them? At the heart of computer program design are two goals. To design an algorithm that is easy to understand, code, debug. To design an algorithm that makes efficient use of the computer’s resources. How to Measure Efficiency? 渐近算法分析Asymptotic Algorithm Analysis For most algorithms, running time depends on “size” of the input. Running time is expressed as T(n) for some function T on input size n. Examples of Growth Rate Example 1. // Find largest value int largest(int array[], int n) { int currlarge = 0; // Largest value seen for (int i=1; in; i++) // For each val if (array[currlarge] array[i]) currlarge = i; // Remember pos return currlarge; // Return largest } Examples (cont) Example 2: Assignment statement. Example 3: sum = 0; for (i=1; i=n; i++) for (j=1; jn; j++) sum++; } Best, Worst, Average Cases Not all inputs of a given size take the same time to run. Sequential search for K in an array of n integers: Begin at first element in array and look at each element in turn until K is found Best case: Worst case: Average case: Faster Computer or Algorithm? What happens when we buy a computer 10 times faster? Asymptotic Analysis: Big-