TAILIEUCHUNG - Lecture note Data visualization - Chapter 17

The main contents of the chapter consist of the following: Remaining part of maximum contiguous subsequence sum problem, general big-oh rule, running time of algorithm. | Lecture note Data visualization - Chapter 17 Lecture 17 Recap Remaining Part of Maximum Contiguous Subsequence Sum Problem General Big Oh Rule Big Oh Big Omega Big Theta Little Oh Running Time of Algorithm Running Time of Cubic Algorithm Running Time of Quadratic Algorithm Running Time of Linear Algorithm A similar calculation shows that a 10 fold increase in input size results in a 10 fold increase in running time This relationship has been confirmed experimentally For a linear program the term sufficiently large means a somewhat higher input size than for the other programs The reason is that of the overhead of sec is used in all cases For a linear program this term is still significant for moderate input sizes Running Time of Logarithmic Terms The Logarithm The list of typical growth rate functions includes several entries containing the logarithm A logarithm is the exponent that indicates the power to which a number the base is raised to produce a given number Definition of Logarithm Theorem Logarithm Continued . Bits in a Binary Number Repeated Doubling Repeated Halving Continued . Many of the algorithms contain logarithms because of the repeated halving principle which holds that starting at N we can halve only logarithmically many times In other words an algorithm is O log N if it takes constant O 1 time to cut the problem size by a constant fraction usually 112 This condition follows directly from the fact that there will be O log N iterations of the loop Any constant fraction will do because the fraction is reflected in the base of the logarithm and Theorem tells us that the base does not matter Theorem Static Searching Problem An important use of computers is to look up data If the data are not allowed to change . it is stored on a CD ROM we say that the data are static A static search accesses data that are never altered Problem GIVEN AN INTEGER X AND AN ARRAY A RETURN THE POSITION OF X IN A OR AN INDICATION THAT IT IS NOT .

• Cơ sở dữ liệu
• Data visualization
• Lecture note Data visualization
• Data structures
• Data Visualization with C
• Data visualization with matlab
• Effective graphical display