tailieunhanh - Lecture note Data visualization - Chapter 15

In this lecture we learned about: Overriding a method, static and dynamic binding, virtual function, types of member function, abstract method/abstract class, constructor and destructor: virtual or non-virtual. | Lecture note Data visualization - Chapter 15 Lecture 15 Recap Overriding a Method Static and Dynamic Binding Virtual Function Types of Member Function Abstract Method Abstract Class Constructor and Destructor Virtual or Non Virtual Chapter 6 Algorithm Analysis Introduction In this chapter we study how to estimate the time required for an algorithm how to use techniques that drastically reduce the running time of an algorithm how to use a mathematical framework that more rigorously describes the running time of an algorithm how to write a simple binary search routine Definition An algorithm is a clearly specified set of instructions a computer follows to solve a problem Once an algorithm is given for a problem and determined to be correct the next step is to determine the amount of resources such as time and space that the algorithm will require. This step is called algorithm analysis An algorithm that requires several gigabytes of main memory is not useful for most current machines even if it is completely correct Algorithm Analysis The amount of time that any algorithm takes to run almost always depends on the amount of input that it must process For instance sorting 10 000 elements requires more time than sorting 10 elements The running time of an algorithm is thus a function of the input size The exact value of the function depends on many factors such as the speed of the host machine the quality of the compiler and in some cases the quality of the program. Example 1 The curves represent four common functions encountered in algorithm analysis Linear O N log N Quadratic Cubic The input size N ranges from 1 to 100 items and the running times range from 0 to 10 milliseconds Example 2 Problem of Downloading a File from Suppose that there is an initial 2 sec delay after which the the Internet download proceeds at K sec Then if the file is N kilobytes the time to download is described by the formula T N N 2. This is a linear function Downloading an 80K file