演算法與資料結構超入門 With JavaScript：Frequency Counter 範例
去年年末開始，固定每週花一些時間，規劃比較有系統性的資結與演算法學習，目前是透過書籍與 udemy 的這堂課來學習。以下簡單做一點紀錄：
演算法是什麼？資料結構是什麼？為何需要他們？
如果先不管程式上的問題，在生活中，我們經常都會為了一個想達成的目標，付出一些行動。例如假日放鬆想看一部電影，你可以去出租店租片，或是借朋友的 netflix 帳號，如果沒朋友的話就自己辦一個，或是下載盜版的。
程式的世界也是如此，同樣的問題可用多種不同的方式加以解決，因此需要一些共同的標準來衡量各種方法的好壞。
解決問題的方法，就是演算法。而為了解決問題，所儲存訊息的地方與方式，就是資料結構。
在演算法中，通常使用 Space Complextiy 與 Time Complextiy 來衡量一個演算法的好壞。根據這個函式隨著輸入的資料量增加時，執行時間與佔據的記憶體空間會“增加多少”以及”如何增加“來作為衡量的標準。
補充說明：
常聽到的 Big O Notation ，代表的是演算法函式的上限（Upper bound），表示在處理規模為 n 的問題時，當 n 趨近無限的狀況下，演算法的執行衡量只需關注某個項目，其餘的部分可忽略不計，這時就以 Big-Ο 來代表這個關注的剩餘項。接著，直接進入第一個基本的方法示範。
Frequency Counter
題目：給定兩個字串，寫一個函數，判斷第二個字串是否為第一個字串的重新組合，例如：appple & plpea，這兩組字都由同樣的字、同樣的字數組成。例如：
validAnagram('rat', 'cat') // 應該 return false
validAnagram('cinema', 'iceman') /// 應該 return true
首先，如果完全不理會什麼演算法、資結，單純以一個”會語法”的前提，可能會寫出這樣的解法：
首先將為了把字串與字串做比對時，可以將已經比對過的字刪除，當發現在第二個字串中找不到某一個字時，直接回傳 false，檢查到最後，回傳 true。
首先，將兩個字串都轉換為陣列，要個跑一次完整的迴圈，這個動作的時間複雜度是 O(n)，因為會隨著字串的越長，迴圈要跑越多次。
再來是以第一個字串形成的陣列去跑迴圈，這也是 O(n)，而當中的每一次迴圈，都會以第二個字串形成的陣列跑一次 findIndex()，由於這個原生方法也是從第一個元素開始查找，找到才跳出，因此也是 O(n)，當找到的話，要將這個元素從第二個字串形成的陣列中刪除，對陣列執行splice(index, 1)，這也是一次O(n)。
因此整個函數是O(n) * O(n) ，n 平方的時間複雜度。
可能覺得 n 平方跑起來”感覺‘還是不慢，但事實是，當中隱含了許多重複、不必要的動作，是可以被節省起來的。
以這題來說，對第一個字串陣列跑迴圈時，每一次都去“遍歷”的檢查第二個字串陣列，有沒有相同的字。那其實可以一次把第二個字串中所有的字詞資訊記錄起來，當我能夠”快速取得“第二個字串的資訊，執行的速度就會更快。
有了這個想法後，接著問題來了？我該怎麼存第二個字串的資訊呢？畢竟這些資訊待會必須要能夠被“快速取得”，才有其價值。
儲存多種、多個資訊，基本上會利用陣列或物件，那陣列是連續的記憶體位置，以取值動作來說，除非能得知資訊的位子 (index)，否則也是要一個個按順序去找，因此這裏就讓物件登場！
試想，物件是一個固定的記憶體空間，由 key-value pairs 組成，因此只要知道屬性名稱就能快速取得值。
解法如下：
透過一個 mapObj 來存放字串資訊，以字串中的字作為屬性，並儲存字串出現的次數，再以另一個字詞來跑迴圈，直接以字對 mapObj 取值，如果有值的話，就將 mapObj 對應的值減一，表示這個字已出現過一次，如果取值結果為 undefined ，表示這個字沒有出現過、或是對應出現的次數超過了，因此就代表兩個字並非同一個字串的重新組合。
以這個方法，就是對輸入的兩個字串各跑一次迴圈，時間複雜度因此是 O(n)。(隨著輸入字串的大小 n，迴圈執行的次數同樣變為 n 次)。
以上就是 Frequency Counter 的簡單示範，下一篇會紀錄 multiple pointer 。
