Lecture note Data visualization - Chapter 17

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

Thêm vào BST

Báo xấu

11
lượt xem 1
download

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

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.

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 17

Lecture 17
Recap Remaining Part of Maximum Contiguous Subsequence Sum Problem General BigOh Rule BigOh BigOmega BigTheta LittleOh 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 10fold increase in input size results in a 10fold 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 0.000003 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 6.4
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 6.4 tells us that the base does not matter
Theorem 6.5
Static Searching Problem An important use of computers is to look up data If the data are not allowed to change (e.g., it is stored on a CDROM), 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 PRESENT. IF X OCCURS MORE THAN ONCE, RETURN ANY OCCURRENCE. THE ARRAY A IS NEVER ALTERED.
Solution An example of static searching is looking up a person in the telephone book The efficiency of a static searching algorithm depends on whether the array being searched is sorted In the case of the telephone book, searching by name is fast, but searching by phone number is hopeless Some solution Sequential Search Binary Search 
Sequential Search When the input array has not been sorted, we have little choice but to do a linear sequential search that steps through the array sequentially until a match is found The complexity of the algorithm is analyzed in three ways First, we provide the cost of an unsuccessful search Second, we give the worstcase cost of a successful search Finally, we find the average cost of a successful search Analyzing successful and unsuccessful searches separately is typical 
Continued…. An unsuccessful search requires the examination of every item in the array, so the time will be O(N) In the worst case, a successful search, too, requires the examination of every item in the array because we might not find a match until the last item. Thus the worstcase running time for a successful search is also linear On average, however, we search only half an array. That is, for every successful search in position i, there is a corresponding successful search in position N1i However, N/2 is still O(N)