官網總結
INTRO
研究算法是為了減少計算機運作時間進而降低成本
比如FFT（快速傅裡葉算法）。an algorithm for breaking down the wave form of n samples of a signal into periodic components.将信号的N個采樣波形分為若幹周期分量 And that’s at the basis for dvds and jpegs and, and many other appl ications. There’s an easy way to do it that takes time proportional to N^2. But the FFT algorithm, takes only N log N steps. And the difference between N log N and N^2 is, is the difference between being able to solve a large problem and not being able to solve it.
又比如N body simulation problem N體仿真問題。The easy algorithm takes time proportional to N^2, but Appel’s algorithm was an N log N algorithm that again, meant that scientists can do N body simulation for huge values of N.
OBSERVATIONS
例
如果代碼是這樣的，怎麼計算需要多久
可以用java自帶函數
根據實踐測試，發現運作時間和資料數量呈現幂定律 power law
當得到這個模型時，可以根據公式predict運作N個樣本需要花多久，不用再實際運作。
除了system independent effects (algorithm和input data），實際的運作時間還由system dependent effects包括hardware, software, system等決定。
MATHEMATICAL MODELS
The total running time of a program is determined by two primary factors: the cost of executing each statement and the frequency of execution of each statement.
我們需要知道：加減乘除、取整、三角函數、length()等基礎函數分别需要多久nanoseconds納秒
注意：連接配接字元串string concatenation的時間和字元串長度成正比，而非常數操作時間
但是每個細節都考慮的話太麻煩了，是以現在都是 rather than going in and counting every little detail, we take some basic operation that’s maybe the most expensive and or the one that’s executed the most often, and the one that costs time frequency is the highest, and use that as a proxy for the running time.
在上面這個2-sum的例子中我們選擇array access用來估計running time。
經過以上2個簡化的步驟，我們現在可以估計2-sum的運作時間約為aN^2。
同理，對于3-sum，3CN ~ 1/6N^3。 tilde it for each triple每個3整數組通路資料組三次，得到~ 1/2N^3。
Order-of-Growth Classifications
從上圖可以看出log算法的優越性，即使size很大log需要花的時間也很小。當linear或者NlogN的時候，時間和size成正比，這時就要考慮input data的數量了。
【例】binary search：給一個有序整數數組和一個值，想知道這個值在數組中是否存在，在什麼位置。代碼如下
證明：根據遞歸關系，T(N)~logN
用binary search優化3-sum算法
N^2logN 比 N^3 好
Theory of Algorithms
在現實中，會有best case (determined by easiest input), worst case, average case. 為了适應客戶需求，需要知道input對運作時間的影響。
兩種解決辦法
MEMORY
float單精度浮點 long長整型 double雙精度浮點
總結