[ Intro Alg ] Getting Started - Analyzing algorithms

Preface: (p44) 
Analyzing an algorithm has come to mean predicting the resources that the algorithm requires. Occasionally, resources such as memory, communication bandwidth, or computer hardware are of primary concern, but most often it is computational time that we want to measure. Generally, by analyzing several candidate algorithms for a problem, we can identify a most efficient one. 

Before we can analyze an algorithm, we must have a model of the implementation technology that we will use, including a model for the resources of that technology and their costs. For most of this book, we shall assume a generic one-processor, random-access machine (RAM) model of computation as our implementation technology and understand that our algorithms will be implemented as computer programs. In the RAM model, instructions are executed one after another, with no concurrent operations.

Analyzing even a simple algorithm in the RAM model can be a challenge. The mathematical tools required may include combinatorics, probability theory, algebraic dexterity, and the ability to identify the most significant terms in a formula. Because the behavior of an algorithm may be different for each possible input, we need a means for summarizing that behavior in simple, easily understood formulas. 

Even though we typically select only one machine model to analyze a given algorithm, we still face many choices in deciding how to express our analysis. We would like a way that is simple to write and manipulate, shows the important characteristics of an algorithm’s resource requirements, and suppresses tedious details. 

Analysis of insertion sort: 
The time taken by the INSERTION-SORT procedure depends on the input: sorting a thousand numbers takes longer than sorting three numbers. Moreover, INSERTION-SORT can take different amounts of time to sort two input sequences of the same size depending on how nearly sorted they already are. In general, the time taken by an algorithm grows with the size of the input, so it is traditional to describe the running time of a program as a function of the size of its input. To do so, we need to define the terms “running time” and “size of input” more carefully. 

The best notion for input size depends on the problem being studied. For many problems, such as sorting or computing discrete Fourier transforms, the most natural measure is the number of items in the input—for example, the array size n for sorting. For many other problems, such as multiplying two integers, the best measure of input size is the total number of bits needed to represent the input in ordinary binary notation. Sometimes, it is more appropriate to describe the size of the input with two numbers rather than one. For instance, if the input to an algorithm is a graph, the input size can be described by the numbers of vertices and edges in the graph. We shall indicate which input size measure is being used with each problem we study. 

The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed. It is convenient to define the notion of step so that it is as machine-independent as possible. For the moment, let us adopt the following view. A constant amount of time is required to execute each line of our pseudocode. One line may take a different amount of time than another line, but we shall assume that each execution of the ith line takes time ci , where ci is a constant. This viewpoint is in keeping with the RAM model, and it also reflects how the pseudocode would be implemented on most actual computers. 

The following discussion, our expression for the running time of INSERTION-SORT will evolve from a messy formula that uses all the statement costs ci to a much simpler notation that is more concise and more easily manipulated. This simpler notation will also make it easy to determine whether one algorithm is more efficient than another. 

We start by presenting the INSERTION-SORT procedure with the time “cost” of each statement and the number of times each statement is executed. For each j=2,3,...,n,where n = A.length, we let tj denote the number of times the while loop test in line 5 is executed for that value of j . When a for or while loop exits in the usual way (i.e., due to the test in the loop header), the test is executed one time more than the loop body. 
 

The running time of the algorithm is the sum of running times for each statement executed; a statement that takes ci steps to execute and executes n times will contributeci*n to the total running time. To compute T(n), the running time of INSERTION-SORT on an input of n values, we sum the products of the cost and times columns, obtaining: 
 

Even for inputs of a given size, an algorithm’s running time may depend on which input of that size is given. For example, in INSERTION-SORT, the best case occurs if the array is already sorted. For each j = 2,3,...,n, we then find that A <= key in line 5 when [i]i has its initial value of j-1. Thus tj=1 for j=2,3,...,n, and the best-case running time is: 
 

We can express this running time as a*n+b for constants a and b that depend on the statement costs ci ; it is thus a linear function of n. 

If the array is in reverse sorted order—that is, in decreasing order—the worst case results. We must compare each element A[j]  with each element in the entire sorted subarray A[1,...,j-1] , and so tj=j for j=2,3,...,n. Noting that 
 

we find that in the worst case, the running time of INSERTION-SORT is 
 

The worst-case running time is a*n^2 + b*n + c for constants a, b, and c that again depend on the statement costs ci ; it is thus a quadratic function of n. 

Worst-case and average-case analysis: 
In our analysis of insertion sort, we looked at both the best case, in which the input array was already sorted, and the worst case, in which the input array was reverse sorted. For the remainder of this book, though, we shall usually concentrate on finding only the worst-case running time, that is, the longest running time for any input of size n. We give three reasons for this orientation. 
- Upper bound of running time 

The worst-case running time of an algorithm gives us an upper bound on the running time for any input. Knowing it provides a guarantee that the algorithm will never take any longer. We need not make some educated guess about the running time and hope that it never gets much worse.

- Performance evaluate 

For some algorithms, the worst case occurs fairly often. For example, in searching a database for a particular piece of information, the searching algorithm’s worst case will often occur when the information is not present in the database. In some applications, searches for absent information may be frequent.

- Average case 

The “average case” is often roughly as bad as the worst case. Suppose that we randomly choose n numbers and apply insertion sort. How long does it take to determine where in subarray A[1.. j-1] to insert element A[j] On average, half the elements in A[1..j-1] are less than A[j]  , and half the elements are greater. On average, therefore, we check half of the subarray A[1..j-1] , and so tj is about j/2. The resulting average-case running time turns out to be a quadratic function of the input size, just like the worst-case running time.

Order of growth: 
We used some simplifying abstractions to ease our analysis of the INSERTION-SORT procedure. First, we ignored the actual cost of each statement, using the constantsci to represent these costs. Then, we observed that even these constants give us more detail than we really need: we expressed the worst-case running time as a*n^2 + b*n + c for some constants a, b, and c that depend on the statement costs ci. We thus ignored not only the actual statement costs, but also the abstract costs ci. 

We shall now make one more simplifying abstraction: it is the rate of growth, or order of growth, of the running time that really interests us. We therefore consider only the leading term of a formula (e.g., an^2), since the lower-order terms are relatively insignificant for large values of n. We also ignore the leading term’s constant coefficient, since constant factors are less significant than the rate of growth in determining computational efficiency for large inputs. For insertion sort, when we ignore the lower-order terms and the leading term’s constant coefficient, we are left with the factor of n^2 from the leading term. We write that insertion sort has a worst-case running time of ‚Θ(n^2)(pronounced “theta of n-squared”). We shall use ‚Θ-notation informally in this chapter, and we will define it precisely in Chapter 3. 

We usually consider one algorithm to be more efficient than another if its worst-case running time has a lower order of growth. Due to constant factors and lower-order terms, an algorithm whose running time has a higher order of growth might take less time for small inputs than an algorithm whose running time has a lower order of growth. But for large enough inputs, a ‚Θ(n^2) algorithm, for example, will run more quickly in the worst case than a ‚Θ(n^3) algorithm.

[ C/C++ 文章收集 ] system("pause") for linux

來源自 這裡 
Preface: 
在windows底下如果不想藉由開發工具做debug時，筆者我多數使用system("pause")這個指令，但是一到了linux之後，這個指令完全無效，因為linux的termainl底下本來就沒有這個指令，面對這樣的問題，網路上有一堆解決方式，這裡提供筆者我自己常用的方法. 

方案一: 

view plaincopy to clipboardprint?

1. #include   
2. #define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);  
3. int main(void)  
4. {  
5.     PAUSE  
6.     printf("system(\"pause\") for linux!\n");  
7.     return 0;  
8. }  

可以看到我只是簡單的使用兩個指令來達到一樣的效果，我還用#define給預先定義起來，如此一來我每次要使用只需要打上PAUSE即可。 
當然如果你夠懶的話，就把他寫成header file，以後要使用就載入header file來使用. 

方案二: 
直接產生一個類似pause的程式，然後把他放在 /usr/bin 裡面，pause的實做程式碼如下: 

view plaincopy to clipboardprint?

1. #include   
2. void main(void)  
3. {  
4.     printf("Press Enter key to continue...");  
5.     fgetc(stdin);  
6. }  

如此一來你就可以直接在程式碼裡使用 system("pause");了。 
PS. fgetc() 必須讀到 Enter 的keycode才會終止當下的輸入，如果你要達到完全的任意按鍵就執行下一行，可以參考 [C/C++] getch() for linux.

[ Intro Alg ] Getting Started - Insertion sort

Preface: 
Here we will familiarize you with the framework we shall use throughout the book to think about the design and analysis of algorithms. It is self-contained, but it does include several references to material that we introduce in Chapters 3 and 4. 

We begin by examining the insertion sort algorithm to solve the sorting problem introduced in Chapter 1. We define a “pseudocode” that should be familiar to you if you have done computer programming, and we use it to show how we shall specify our algorithms. Having specified the insertion sort algorithm, we then argue that it correctly sorts, and we analyze its running time. The analysis introduces a notation that focuses on how that time increases with the number of items to be sorted. 

Insertion sort: 
Our first algorithm, insertion sort, solves the sorting problem introduced in Chapter 1: 
 

The numbers that we wish to sort are also known as the keys. Although conceptually we are sorting a sequence, the input comes to us in the form of an array with nelements. Here we shall typically describe algorithms as programs written in a pseudocode that is similar in many respects to C, C++, Java, Python, or Pascal. If you have been introduced to any of these languages, you should have little trouble reading our algorithms. What separates pseudocode from “real” code is that in pseudocode, we employ whatever expressive method is most clear and concise to specify a given algorithm. Sometimes, the clearest method is English, so do not be surprised if you come across an English phrase or sentence embedded within a section of “real” code. Another difference between pseudocode and real code is that pseudocode is not typically concerned with issues of software engineering. Issues of data abstraction, modularity, and error handling are often ignored in order to convey the essence of the algorithm more concisely. 

We start with insertion sort, which is an efficient algorithm for sorting a small number of elements. Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left, as illustrated in Figure 2.1. At all times, the cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table. 
 

We present our pseudocode for insertion sort as a procedure called INSERTION-SORT, which takes as a parameter an array A[1..n ] containing a sequence of length nthat is to be sorted. (In the code, the number n of elements in A is denoted by A.length.) The algorithm sorts the input numbers in place: it rearranges the numbers within the array A, with at most a constant number of them stored outside the array at any time. The input array A contains the sorted output sequence when the INSERTION-SORT procedure is finished. 

Loop invariants and the correctness of insertion sort: 
 

Figure 2.2 shows how this algorithm works for A=[5, 2, 4, 6, 1, 3]. The index j indicates the “current card” being inserted into the hand. At the beginning of each iteration of the for loop, which is indexed by j , the subarray consisting of elements A[1..j-1 ] constitutes the currently sorted hand, and the remaining subarray A[j+1..n] corresponds to the pile of cards still on the table. In fact, elements A[1..j-1] are the elements originally in positions 1 through j  1, but now in sorted order. We state these properties of A[1..j-1]  formally as a loop invariant. 

We use loop invariants to help us understand why an algorithm is correct. We must show three things about a loop invariant: 
- Initialization 

It is true prior to the first iteration of the loop.

- Maintenance 

If it is true before an iteration of the loop, it remains true before the next iteration.

- Termination 

When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

When the first two properties hold, the loop invariant is true prior to every iteration of the loop. (Of course, we are free to use established facts other than the loop invariant itself to prove that the loop invariant remains true before each iteration.) Note the similarity to mathematical induction, where to prove that a property holds, you prove a base case and an inductive step. Here, showing that the invariant holds before the first iteration corresponds to the base case, and showing that the invariant holds from iteration to iteration corresponds to the inductive step. 

The third property is perhaps the most important one, since we are using the loop invariant to show correctness. Typically, we use the loop invariant along with the condition that caused the loop to terminate. The termination property differs from how we usually use mathematical induction, in which we apply the inductive step infinitely; here, we stop the “induction” when the loop terminates. 

Let us see how these properties hold for insertion sort. 
- From Initialization 

We start by showing that the loop invariant holds before the first loop iteration, when j=2. The subarray A[1.. j-1] , therefore, consists of just the single element A[1] , which is in fact the original element in A[1]. Moreover, this subarray is sorted (trivially, of course), which shows that the loop invariant holds prior to the first iteration of the loop.

- From Maintenance 

Next, we tackle the second property: showing that each iteration maintains the loop invariant. Informally, the body of the for loop works by moving A[j-1] , A[j-2] , A[j-3] (while loop) , and so on by one position to the right until it finds the proper position for A[j]  (lines 4–7), at which point it inserts the value of A[j]  (line 8). The subarray A[1..j]  then consists of the elements originally in A[1..j]  , but in sorted order. Incrementing j for the next iteration of the for loop then preserves the loop invariant.

- From Termination 

Finally, we examine what happens when the loop terminates. The condition causing the for loop to terminate is that j > A.length=n. Because each loop iteration increases j by 1, we must have j=n+1 at that time. Substituting n+1 for j in the wording of loop invariant, we have that the subarray A[1..n] consists of the elements originally in A[1..n] , but in sorted order. Observing that the subarray A[1..n] is the entire array, we conclude that the entire array is sorted. Hence, the algorithm is correct.

Implementation in C: 
Below is the implementation of Insert sort in C: 
- SortAlg.h 

view plaincopy to clipboardprint?

1. #ifndef __SORT_ALG__  
2. #define __SORT_ALG__  
3. #include   
4. using namespace std;  
5.   
6. void insertionSort(vector<int> & arr);  
7.   
8. #endif  

- SortAlg.cpp 

view plaincopy to clipboardprint?

1. #include "SortAlg.h"  
2.   
3.    
4. void swap(vector & arr, int i, int j) {    
5.     Comparable tmp = arr[i];    
6.     arr[i] = arr[j] ; arr[j] = tmp;    
7. }    
8.   
9. void insertionSort(vector<int> & arr)  
10. {  
11.     int j;  
12.     for(int i=1; i
13.     {  
14.         int key = arr[i];  
15.         j=i-1;  
16.         while(j>=0 && arr[j]>key)  
17.         {  
18.             swap(arr, j, j+1);  
19.             j--;  
20.         }  
21.     }  
22. }  

- main.cpp: 

view plaincopy to clipboardprint?

1. #include "SortAlg.h"  
2. #include   
3. using namespace std;  
4.   
5. void main()  
6. {  
7.     vector<int> ivector;  
8.     ivector.push_back(5);  
9.     ivector.push_back(2);  
10.     ivector.push_back(4);  
11.     ivector.push_back(6);  
12.     ivector.push_back(1);  
13.     ivector.push_back(3);  
14.     printf("\t[Info] Original vector: [");  
15.     for(vector<int>::iterator it = ivector.begin(); it!=ivector.end(); it++) printf("%d ", *it);  
16.     printf("]\n");  
17.     insertionSort(ivector);  
18.     printf("\t[Info] After insertSort: [");  
19.     for(vector<int>::iterator it = ivector.begin(); it!=ivector.end(); it++) printf("%d ", *it);  
20.     printf("]\n");  
21. }  

Execution output: 

[Info] Original vector: [5 2 4 6 1 3 ]
[Info] After insertSort: [1 2 3 4 5 6 ]

Supplement: 
* [ Data Structures with Java ] Section 7.1 : Insertion Sort