Lecture note Data visualization - Chapter 18

Chia sẻ: Minh Nhật | Ngày: | Loại File: PPTX | Số trang:33

Thêm vào BST

Báo xấu

16
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

This chapter presents the following content: Running time of function, running time of cubic function, running time of quadratic function, running time of linear function, running time of logarithmic function, logarithm, static searching problem,...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lecture note Data visualization - Chapter 18

Lecture 18
Recap Running Time of Function Running Time of Cubic Function Running Time of Quadratic Function Running Time of Linear Function Running Time of Logarithmic Function Logarithm Bits in Binary Numbers Repeated Doubling Repeated Halving
Checking an Algorithm Analysis Once we have performed an algorithm analysis, we want to determine whether it is correct and as good we can possibly make it One way to do so is to code the program and see if the empirically observed running time matches the running time predicted by the analysis
Continued…. When N increases by a factor of 10, the running time goes up by a factor of 10 for linear programs, 100 for quadratic programs, and 1000 for cubic programs Programs that run in O(N log N) take slightly more than 10 times as long to run under the same circumstances These increases can be hard to spot if the lower order terms have relatively large coefficients and N is not large enough  An example is the jump from N = 10 to N = 100 in the running time for the various implementations of the maximum contiguous subsequence sum problem
Continued…. Another commonly used trick to verify that some program is O(F(N)) is to compute the values T(N)/F(N) for a range of N, where T(N) is the empirically observed running time If F(N) is a tight answer for the running time, the computed values converge to a positive constant If F(N) is an overestimate, the values converge to zero If F(N) is an underestimate, and hence wrong, the values diverge
Example
Empirical running time for N binary searches in an Nitem array
Continued…. Note in particular that we do not have definitive convergence One problem is that the clock that we used to time the program ticks only every 10 ms Note also that there is no great difference between O(N) and O(N log N) Certainly an O(N log N) algorithm is much closer to being linear than being quadratic Finally, note that the machine in this example has enough memory to store 640,000 objects
Limitations of BigOh Analysis BigOh analysis is a very effective tool, but it does have limitations Its use is not appropriate for small amounts of input For small amounts of input, use the simplest algorithm Also, for a particular algorithm, the constant implied by the BigOh may be too large to be practical For example: if one algorithm's running time is governed by the formula 2N log N and another has a running time of 1000N, the first algorithm would most likely be better, even though its growth rate is larger
Continued…. Large constants can come into play when an algorithm is excessively complex They also come into play because our analysis disregards constants and thus cannot differentiate between things like memory access and disk access Our analysis assumes infinite memory, but in applications involving large data sets, lack of sufficient memory can be a severe problem
Continued…. Sometimes, even when constants and lower order terms are considered, the analysis is shown empirically to be an overestimate In this case, the analysis needs to be tightened. Or the averagecase running time bound may be significantly less than the worstcase running time bound, and so no improvement in the bound is possible For many complicated algorithms the worstcase bound is achievable by some bad input, but in practice it is usually an overestimate Two examples:
Continued…. However, worstcase bounds are usually easier to obtain than their averagecase counterparts For example: a mathematical analysis of the averagecase running time of Shellsort has not been obtained Sometimes, merely defining what average means is difficult We use a worstcase analysis because it is expedient and also because, in most instances, the worstcase analysis is very meaningful In the course of performing the analysis, we frequently
Summary of Chapter In this chapter we introduced algorithm analysis and showed that algorithmic decisions generally influence the running time of a program much more than programming tricks do We also showed the huge difference between the running times for quadratic and linear programs and illustrated that cubic algorithms are, for the most part, unsatisfactory We examined an algorithm that could be viewed as the basis for our first data structure The binary search efficiently supports static operations thereby providing a logarithmic worstcase search
Common Errors
Continued….
Data Structures and Algorithms with Matlab
MATLAB Environment
MATLAB opening window
MATLAB Windows Command window Command History Workspace Window Current Folder Window Document Window Graphics Window Edit Window Start Button
Command Window The command window is located in the center pane of the default view of the MATLAB screen The command window offers an environment similar to a scratch pad Using it allows you to save the values you calculate, but not the commands used to generate those values If you want to save the command sequence, you will need to use the editing window to create an Mfile. Both approaches are valuable.