第01章算法分析Analysis.ppt
《第01章算法分析Analysis.ppt》由会员分享,可在线阅读,更多相关《第01章算法分析Analysis.ppt(28页珍藏版)》请在三一文库上搜索。
1、Analysis of Algorithms,Algorithm,Input,Output,An algorithm is a step-by-step procedure for solving a problem in a finite amount of time.,Analysis of Algorithms,2,Running Time (1.1),Most algorithms transform input objects into output objects. The running time of an algorithm typically grows with the
2、input size. Average case time is often difficult to determine. We focus on the worst case running time. Easier to analyze Crucial to applications such as games, finance and robotics,Analysis of Algorithms,3,Experimental Studies ( 1.6),Write a program implementing the algorithm Run the program with i
3、nputs of varying size and composition Use a method like System.currentTimeMillis() to get an accurate measure of the actual running time Plot the results,Analysis of Algorithms,4,Limitations of Experiments,It is necessary to implement the algorithm, which may be difficult Results may not be indicati
4、ve of the running time on other inputs not included in the experiment. In order to compare two algorithms, the same hardware and software environments must be used,Analysis of Algorithms,5,Theoretical Analysis,Uses a high-level description of the algorithm instead of an implementation Characterizes
5、running time as a function of the input size, n. Takes into account all possible inputs Allows us to evaluate the speed of an algorithm independent of the hardware/software environment,Analysis of Algorithms,6,Pseudocode (1.1),High-level description of an algorithm More structured than English prose
6、 Less detailed than a program Preferred notation for describing algorithms Hides program design issues,Analysis of Algorithms,7,Pseudocode Details,Control flow if then else while do repeat until for do Indentation replaces braces Method declaration Algorithm method (arg , arg) Input Output ,Method c
7、all var.method (arg , arg) Return value return expression Expressions Assignment (like in Java) Equality testing (like in Java) n2 Superscripts and other mathematical formatting allowed,Analysis of Algorithms,8,The Random Access Machine (RAM) Model,A CPU An potentially unbounded bank of memory cells
8、, each of which can hold an arbitrary number or character,Memory cells are numbered and accessing any cell in memory takes unit time.,Analysis of Algorithms,9,Primitive Operations,Basic computations performed by an algorithm Identifiable in pseudocode Largely independent from the programming languag
9、e Exact definition not important (we will see why later) Assumed to take a constant amount of time in the RAM model,Examples: Evaluating an expression Assigning a value to a variable Indexing into an array Calling a method Returning from a method,Analysis of Algorithms,10,Counting Primitive Operatio
10、ns (1.1),By inspecting the pseudocode, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input size,Algorithm arrayMax(A, n) # operations currentMax A0 2 for i 1 to n 1 do 2 + n if Ai currentMax then 2(n 1) currentMax Ai 2(n 1) increment count
11、er i 2(n 1) return currentMax 1 Total 7n 1,Analysis of Algorithms,11,Estimating Running Time,Algorithm arrayMax executes 7n 1 primitive operations in the worst case. Define: a = Time taken by the fastest primitive operation b = Time taken by the slowest primitive operation Let T(n) be worst-case tim
12、e of arrayMax. Then a (7n 1) T(n) b(7n 1) Hence, the running time T(n) is bounded by two linear functions,Analysis of Algorithms,12,Growth Rate of Running Time,Changing the hardware/ software environment Affects T(n) by a constant factor, but Does not alter the growth rate of T(n) The linear growth
13、rate of the running time T(n) is an intrinsic property of algorithm arrayMax,Analysis of Algorithms,13,Growth Rates,Growth rates of functions: Linear n Quadratic n2 Cubic n3 In a log-log chart, the slope of the line corresponds to the growth rate of the function,Analysis of Algorithms,14,Constant Fa
14、ctors,The growth rate is not affected by constant factors or lower-order terms Examples 102n + 105 is a linear function 105n2 + 108n is a quadratic function,Analysis of Algorithms,15,Big-Oh Notation (1.2),Given functions f(n) and g(n), we say that f(n) is O(g(n) if there are positive constants c and
15、 n0 such that f(n) cg(n) for n n0 Example: 2n + 10 is O(n) 2n + 10 cn (c 2) n 10 n 10/(c 2) Pick c = 3 and n0 = 10,Analysis of Algorithms,16,Big-Oh Example,Example: the function n2 is not O(n) n2 cn n c The above inequality cannot be satisfied since c must be a constant,Analysis of Algorithms,17,Mor
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 01 算法 分析 Analysis
链接地址:https://www.31doc.com/p-2565356.html