Chapter 1
本章結構
1.1Java語法
1.2數據抽象
1.3集合類抽象數據類型：背包 (Bags) 、隊列 (Queues) 、棧 (Stacks)
1.4算法分析
1.5連通性問題－Case Study: Union - Find ADT
?
本節開篇使用了一個ThreeSum程序進行示例：
ThreeSum所起到的作用為Count the number of triples in a file of N integers that sum to 0,簡單來說，就是從N個數里面取3個數的組合，統計這些組合和為零的數量。
?
public class ThreeSum {public static int count(int[] a){int N = a.length;int cnt = 0;for (int i = 0; i < N; i++)for (int j = i+1; j < N; j++)for (int k = j+1; k < N; k++)if (a[i]+a[j]+a[k] == 0)cnt++;return cnt;}public static void main(String[] args){int[] a = In.readInts(args[0]);StdOut.println(count(a));} }
?
與此同時，我們需要一個計時器來確定程序運行的時間，書上給出了一種計時器的實現方案，大概就是先在算法程序開始運行前先記錄當前的系統時間，當算法運算完畢后，再次記錄當前的系統時間，然后對兩個時間進行時間差的運算便可得到整個算法所消耗的時間。
?
public class StopWatch {private final long start;public StopWatch(){ start = System.currentTimeMillis(); }public double elapseTime(){ long now = System.currentTimeMillis();return (now - start) / 1000.0;}public static void main(String[] args){int N = Integer.parseInt(args[0]);int[] a = new int[N];for (int i = 0; i < N; i++)a[i] = StdRandom.uniform(-1000000, 1000000);StopWatch timer = new StopWatch();int cnt = ThreeSum.count(a);double time = timer.elapseTime();StdOut.println(cnt + " triples " + time + " seconds ");} }
?
D.E Knuth認為，一個程序運行的總時間主要和兩點有關：
a.執行每條語句的耗時；
b.執行每條語句的頻率；
如在Threesum.count()中的if語句會執行N(N-1)(N-2)/6次（由排練組合N個選3個可得）
正是這些執行最頻繁的指令決定了程序運行的總時間，而這些指令也被稱為程序的內循環inner loop。許多程序的運行時間往往取決于這一小部分指令的耗時。
ThreeSum運行時間分析
| 語句塊 | 運行時間 | 頻率 | 總時間 |
| cnt++ | t0 | 取決于輸入x | t0*x |
| for對k的循環 | t1 | N取3的組合數 | t1*C N 3 |
| for對j的循環 | t2 | N取2的組合數 | t2*C N 2 |
| for對i的循環 | t3 | N | t3*N |
| count方法 | t4 | 1 | t4 |
| 總時間 | 上述匯總求和 | ||
| 近似 | ~(t1/6)N^3 | ||
| 增長的數量級 | N^3 |
?
至于如何對一些數學模型進行總時間的計算，作者也給了微積分方面的相應解決方案，個人覺得比用數列求和的方式做高級點。
事實上，為任何程序建立數學模型從理論上來說都是可行的，只不過有時候處理過程和方法會變得很復雜。
?
?
-----------------------------------------------------------------------------------------------------------------------
小結：
對于大多數程序，得到其運行時間的數學模型的步驟如下：
1.確定輸入模型input model，定義問題的規模。如在ThreeSum中，輸入規模即是標準輸入中大小為N的整型數組a[N]。
2.識別內循環inner loop。對應回ThreeSum的例子，內循環便是三層的for循環。
3.根據內循環中的操作確定成本模型。所謂成本模型，即是算法中的基本操作。如ThreeSum的成本模型則是對數組元素的訪問次數。
4.對于給定的輸入，判斷這些操作的執行效率。
)
)
