寫給我自己看的資料結構筆記-演算法分析
上篇提到了 ArrayList 與 LinkedList，不同的應用使用不同的 List interface 在執行速度上可能會有差異。這篇文章我們會簡單談一下，要如何知道程式適合使用哪種實作。
性能分析
性能分析即是實際跑一遍，就知道性能如何，結果一目瞭然，但容易受到以下幾個因素影響測試結果：
- 有多少種，我們就需要做多少種，接著才能做分析。
- 硬體會影響分析，不同的硬體可能會有不同的結果，可能這台電腦Ａ比較快，另一台電腦變成Ｂ比較快。
- 分析結果會受到規模會輸入資料的影響。
演算法分析
演算法分析可以在不需要實際跑一趟的情況下，藉由比較與計算的方式得到結果，但有一些前提：
- 通常要找出會用到的基礎運算，像是加減乘除，或是比較，計算這些基礎運算要用到的次數
- 避免輸入資料的影響，需要將輸入值結果做平均，或是取最差的結果。舉例來說一個 100x100的巢狀迴圈，其中要做判斷，我有可能在 1x1 的時候就滿足條件而跳出迴圈，因為會有這種的型的發生，通常我們會取最差的結果。
- 需要考量演算法對於小問題表現優良，但對於大問題表現差勁的情況，因為演算法對於小問題在執行時間上的差異可能也不大，但大問題的差距可能會很巨大。
演算法執行時間
常數執行時間(Constant time)
這代表執行時間與輸入數量無關，比方說我們有一個 n 個元素的 Array，我們要取得某一個 index 的數值，例如說 return test[0];，這個動作無論 n 有多大，執行的時間都是一樣的。
線性執行時間(Linear)
這代表執行時間與輸入的數量呈相關，例如我們要把 n 個元素的 Array 內的所有元素作加總，我們就必須存取 n 次，並執行 n-1 次的加法，所做的動作為 2n-1。
平方執行時間(Quadratic)
這代表執行時間與 n^2 相關，例如我們想知道 n 個元素的 Array 中的 element 是否有出現過超過一次，以最簡單的方式，我們需要依序存取 n 個 element，每一個都要做 n-1 次的比較，執行時間就是 n(n-1) = n^2-n。
Big O
- 所有的常數執行時間，都可以被稱為 O(1)。
- 所有的線性執行時間，都可以被稱為 O(n)。
- 所有的平方執行時間，都可以被稱為 O(n^2)。
為什麼呢，以前面的 n^2-n 為例子，當我們 n 是 1,000,000 時，則會得到 1,000,000*1,000,000-1,000,000 的結果，此時後面的 n 就不是那麼重要了，扣掉他也不會影響太多執行時間，重要的是前面的 n^2。
時間複雜度也代表同一個意思，時間複雜度相同的就是屬於同一個 big O 分類的演算法。
結論
總結起來，要選擇使用哪種實作取決於特定應用場景，而要判斷適用的實作方式，可以透過性能分析和演算法分析來做評估。
性能分析可以透過實際執行程式，但受到多種因素影響，包括測試案例的多樣性、硬體差異以及輸入資料規模的影響。演算法分析則可在不實際執行程式的情況下，透過比較和計算得到結果，但需要考慮基礎運算的次數、輸入資料的影響，以及演算法對小問題和大問題的表現。
接著我們提到了演算法執行時間，演算法執行時間的分類包括常數執行時間 O(1)、線性執行時間 O(n)、平方執行時間 O(n^2) 等，而前述提到的 O(1), O(n), O(n^2) 為 Big O 標示法。