新手村導讀 - 10: 基礎演算法

前言

在開始寫文章、整理之前留下的紀錄時，想起剛出社會時也有去面試演算法工程師的職位，然後被電到慘兮兮 XD，把當時面試有碰到的一些題目分享給大家，讓大家可以有點心理準備(?)

基礎題

解釋複雜度

可以分成時間複雜度與空間複雜度去解釋，在此附上簡易版本：

• O(1)：陣列讀取
• O(n)：線性搜尋
• O(log n)：二分搜尋
• O(nlogn)：合併排序
• O(n²)：選擇排序
• O(2^n)：費波那契數列

介紹五大演算法

我想這個內容在大家求學時期應該都有學過了，但當下被問還是突然講不出來。基本上除了窮舉這個不算方法的方法以外，還有貪婪演算法、動態規劃、分治法、回溯法以及分支法。

介紹排序

有蠻多公司都會考這題，會需要你介紹你所記得的排序方法以及他們的複雜度分析。由於種類蠻多的，因此將比較詳細的介紹放在參考資料第 4 點。

介紹 DP

這是一種將問題複雜度下降的方式，將原本的問題切分成小問題去解決，乍聽之下很容易但其實蠻看經驗和技術的，在 Leetcode 中也蠻多題目會需要用 DP 去解決，一樣將相關資料放在參考資料第 5、6 點。

應用題

由於這方面的文章很多 & 內容很長，因此我就不特別列出解法，不然篇幅會被拉的很長，我僅提供我碰過的題目給大家參考。

• 實作費氏數列與複雜度分析
• 如何解決八皇后問題
• 利用蒙地卡羅方法求圓周率

結語

「演算法是要由內而外去思考，而非直接從題目表面去下手。」這是我之前準備面試時在某個部落格上看到的一句話，在此送給有想要當演算法工程師的各位，加油！

參考資料:

1. https://jason-chen-1992.weebly.com/home/time-space-complexity
2. 五大常用演算法總結 - 程式人生 (796t.com)
3. 【Day35】[演算法]-常見的演算法策略Algorithmic Patterns - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天 (ithome.com.tw)
4. 【演算法】排序演算法 Sorting Algorithm - Jason Chen's Blog (weebly.com)
5. 從LeetCode學演算法 - 9 Dynamic Programming (2) | by Chih-Yu Lin | Medium
6. dynamic_programming_2_inclass.pdf (ntu.edu.tw)