Day01-基本介紹

參賽動機

目前人在台中一間公司擔任後端工程師，因為公司使用 Go 開發，所以這次活動就選擇了這門程式語言。個人背景為數學系，對數據分析、演算法、機器學習領域較感興趣。之前下班時間有寫過一些題目，趁這次機會回顧做整理，一方面也練習寫文章。而此系列文預計以 LeetCode 上難度 Easy 的題目為主。

Go語言

Go 是由 Google 開發的一種程式語言，於 2009 年正式推出，至今已超過 10 個年頭，
軟體評價公司 TIOBE 評價為「TIOBE 2016 年最佳語言」。 Go 還有 21 世紀的 C 語言之稱。這邊要正名一下，作者強調該語言正式名稱為 Go，通俗稱呼為 Golang ( The Go Programming Language )，是因為官方網站域名為 https://golang.org/，且用 golang 在網路上比較方便查找資料。
想要入門 Go 語言的話可以查看官網的教學文檔： A Tour of Go。
另外也有線上編譯器可以練習： The Go Playground 。

LeetCode

LeetCode 是一個線上解題系統，支援各種程式語言。裡面有許多類別的題目以及一些定期競賽。我們關注的類別為演算法，LeetCode 收錄的題目多為軟體工程師面試考古題，做完題目提交程式碼會進行測試。在通過測試後，可以看到自己的程式碼運行時間 (Runtime) 以及 記憶體使用量 (Memory Usage) 跟其他過關的程式碼比較排名為何。detail 選項中可以看到其他人的參考程式碼，還有提供討論區與其他使用者交流。LeetCode 個人檔案也會顯示你的通過率 (Acceptance Rate)。
算法為: 程式碼的通過次數/提交次數。刷題時建議先多測試幾組資料再提交，一方面培養嚴謹的習慣，同時也可以讓通過率數據美觀一點。

演算法與複雜度

演算法的基本概念為解決問題的過程。
在能解決該問題的前提下，要怎麼讓自己的程式執行更加有效率，這就是演算法的優化。我們可以透過分析執行的具體步驟來評估演算法的優劣，一般使用漸近時間複雜度 O( ) 來描述執行時間的複雜度 。舉例來說：當輸入的個數為 n ，而分析此演算法後發現需要 4n³+6n 個步驟，當 n 很大時 n 與 n³ 相比可以忽略，所以此演算法時間複雜度用 O(n³) 表示。而我們通常採用此演算法的最糟情況的時間複雜度。此外我們也會評估執行此演算法時所占的記憶體空間來計算空間複雜度。

時間複雜度評估

Example 1 : 要計算 $S_n = \sum_{i=0}^n i = 0 + 1 + 2 + \dots + n = ?$

• 方法I : 逐項相加，共做了 n次加法 ，需要的計算步驟與 n 有關，記為 O(n) 。
• 方法II : 由 級數和公式 可得 $S_n = \frac{n(n+1)}{2}$，只需要做常數次的加法乘法，與 n 的大小無關，記為 O(1)。

Example2: 要計算 $S_n = \sum_{i=0}^n i^2 = 0^2 + 1^2 + 2^2 + \dots + n^2 = ?$

• 方法 I ： 逐項平方再相加，共做了 (n+1) 次乘法和 n 次加法，時間複雜度為 O(n) 。
• 方法 II ：由 級數和公式 可得 $S_n = \frac{n(n+1)(2n+1)}{6}$，時間複雜度為 O(1)。

小結

演算法好壞對程式執行效能影響極大，以執行步驟 n 次與 n² 次為例：
當 n=1000 時，就差了 1000 倍。而我們實務上一般可接受的演算法時間複雜度為 O(n²)。今天的基本介紹就到這邊，下一篇會開始做 LeetCode 上的題目。