今天學(xué)完了Coursera上Princeton的Algorithm的課程，第一周的課程主要包括一個入門問題的講解-UnionFind-和算法復(fù)雜度介紹。

Union-Find

這個問題是這樣的：對于一個序列或者陣列（甚至更高維度的數(shù)據(jù)）而言，怎么找到相連的兩個數(shù)據(jù)或者為數(shù)據(jù)增加一條關(guān)系。

Union：直觀地，我們可以想到直接找到兩個相關(guān)的數(shù)據(jù)，將它們所在的集合進(jìn)行融合。

Find：直觀地，我們定位到需要的兩個數(shù)據(jù)，然后查看它們是不是在一個集合中。

因此，我們明確了這個問題，我們需要考慮需要如何抽象數(shù)據(jù)結(jié)構(gòu)（Data Structure）和算法（Algorithm）。

數(shù)據(jù)結(jié)構(gòu)和算法的考慮：

我們需要的主要數(shù)據(jù)結(jié)構(gòu)是一個記錄每個數(shù)據(jù)和其所在類或者說組。那么我們可以對不同的組建立一個索引，這樣可以直接查到每個數(shù)據(jù)所在的組。這樣的算法我們可以看出，索引很迅速，因?yàn)橹恍枰樘柧涂梢粤耍碏ind比較容易），而對兩個組進(jìn)行合并的時候，這個索引的作用就沒那么大了（即Union比較難）。

因此，我們可以很快地從反面入手。我們可以加快Union的速度，那么另一個思路就是建立一個樹的結(jié)構(gòu)，那么進(jìn)行結(jié)構(gòu)變化的時候一般都比較快。而這樣Find會減慢，因?yàn)槲覀儾荒苤苯铀饕较鄳?yīng)的數(shù)據(jù)，而需要在樹的結(jié)構(gòu)中進(jìn)行查找。

從這個問題和問題解決我們可以看到，解決一個問題需要以下一些步驟：

1. 問題的分析：明確我們需要解決的問題是什么

2. 根據(jù)需求，構(gòu)建數(shù)據(jù)結(jié)構(gòu)并思考建立在這個數(shù)據(jù)結(jié)構(gòu)上的算法

3. 分析之前的數(shù)據(jù)結(jié)構(gòu)和算法，分析其效率，進(jìn)行改進(jìn)。

Algorithm Analysis

1. 時間：統(tǒng)計(jì)方法（Running Time），數(shù)學(xué)模型（與機(jī)器無關(guān)的）

2. 空間：注意計(jì)算機(jī)的規(guī)格，Pending，head等問題。

課程中還出現(xiàn)了一些小問題，比如3-Sum（在一個序列中是否存在3個數(shù)的和為0）。也具體思考這里的一些算法，我得到的啟示是：

1. 如果問題的一部分可以轉(zhuǎn)換為Search的話，結(jié)合Sort可以加速算法。

Programming Assignment

Percolation

問題的描述應(yīng)該很清楚，在很多地方都有，而其應(yīng)用也非常廣泛，比如水利，網(wǎng)絡(luò)等等。在解決這個問題（造成Percolation和統(tǒng)計(jì)Percolation條件）可以使用Union-Find的算法。

因?yàn)榻鼉扇齻€月的編程量都比較小，所以現(xiàn)在開始重新著重練習(xí)編程能力。

首先我完全使用VIM進(jìn)行編碼，放棄使用IDE（除非我需要進(jìn)行特大工程開發(fā)和User Interface的開發(fā)時候使用IDE）。

這樣做的目的是了解各語言（比如現(xiàn)在我重點(diǎn)練習(xí)Java）的庫和編碼錯誤和錯誤率的控制。