iT邦幫忙

2021 iThome 鐵人賽

DAY 4
2
Software Development

LeetCode 雙刀流:Python x JavaScript系列 第 4

如何衡量程式的好與壞?淺談時間複雜度

刷題的重點在於寫出「好的」程式碼

就如同前兩天提到的,比起盲目地刷題更重視的是如何寫出好的程式碼品質。但是,程式碼品質該如何定義,又該要怎麼判斷自己寫出來的程式碼是好還是壞呢?我們在第二天 LeetCode 解題的思考策略與解題地圖 中有提到「刻意優化」的重要性,對於沒有開發的初學者來說,解題時很容易陷入既有的思考框架,也就是說面對相同的題目時很容易進入同一個解法泥淖。透過刷題的練習經驗中,增加自己對於問題與解法的「多元觀點」是相當重要的。所以除了大量刷題之外,適度的進行優化與重構絕對是這個過程裡不可或缺的。除此之外,我也會建議可以參考其他人的解法,去觀察同一個題目的不同切入點。

怎麼評估程式寫得好不好?

「評斷程式能力到什麼階段?」最快的方式就是透過刷題來,不管是幫助開發者確認自己的能力到什麼階段或是提供面試方作為篩選的標準。這邊順帶一提,很多人在學程式的過程花太多時間在吸收但缺乏輸出,當遇到一個比較大的問題時很容易就會卡關。寫程式就跟國高中的數學學習是很類似的,當你背了很多公式但忽略了範例練習,面對到複雜的應用題時反而會不知道公式該如何應用。雖然現在吸收知識的方式變得更容易,也更容易誤以為自己學會了的假象。根據我的經驗,花多少時間吸收知識(例如看書或影片),你至少應該花一到兩倍的時間進行輸出與應用(例如實作或解題)。

一般來說,程式的優化可以分為「更精簡的程式碼」或「更快地執行速度」兩個角度下去著手。資料結構就是在討論怎樣更好的使用變數的方法,實現有效在程式中儲存資料與使用空間;演算法是從時間的角度進行優化,設計一些更精簡、更高效的程式碼與執行流程。

時間複雜度與空間複雜度

接下來,我們更近一步來量化所謂的優化,也就是到底怎樣算「更精簡的程式碼」或「更快地執行速度」。其實好的程式碼不外乎就是從儲存空間與花費時間來衡量,常見的量化方式稱為複雜度,可以再細分成時間複雜度(Time Complexity)與空間複雜度(Space Complexity)。

複雜度 = 程式增長的「趨勢」

時間複雜度是指演算法執行時所需花費的時間,我們通常會用程式指令執行的次數來表示。換句話說,一個程式需執行越多次的程式碼,就表示花費時間越多。空間複雜度用來表示所佔用的記憶體空間,包含固定空間(例如:程式碼、變數與常數)和變動空間(函數呼叫、動態配置或是所需的堆疊空間)。但是實務上我們不會用絕對的「執行次數」 來衡量演算法的執行效率,單純就執行次數可能會因為不同的硬體效能或是不同的指令難度影響,用絕對的「執行次數」 容易失準。

時間複雜度會根據不同的輸入大小,來定義該演算法所執行的指定執行次數(運算次數)。而我們實際上會利用等級(或稱為漸近式表示)的方式來量化這個次數,也就是當程式在不同輸入時執行時所花費的時間都能維持的上限值。其中一個漸近式表示算法稱為 Big O ,是指當程式執行時所花費的時間成長在最差的情況的上限值。換句話說,可以想成一個算法當 n 很大時,所花時間的增長趨勢為何(如下圖)。

我們會將不同的 BigO 分成不同的等級,用來表示可以接受與需要改進:

面對題目的注意事項

最後一段,當我們面對一個題目的時候有三個重點需要確認:

① 題目的輸入與輸出範圍
② 輸入範圍中極端的邊界條件(或是特例)
③ 所可以接受的時間/空間複雜度

有些題目並不會把這三個重點寫得很明確,可能需要多方推敲。所以不管你是在面試當下面對面試官的解題或平常在練習刷題時,透過「對話」釐清需求、發想解法都有助於對題目有更深的了解。


嗨,大家好!我是維元,一名擅長網站開發與資料科學的雙棲工程師,斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師,同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗,持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享,邀請你加入 訂閱 接收最新資訊。


上一篇
題目背後的設計思維 - 資料結構與演算法
下一篇
踏入 LeetCode 的第一步 - 操作與使用
系列文
LeetCode 雙刀流:Python x JavaScript30
0
TD
iT邦新手 4 級 ‧ 2021-09-19 21:32:50

因此跟我經驗

根據我的經驗 (?)

1
TD
iT邦新手 4 級 ‧ 2021-09-19 21:33:45

花多少時間吸收知識(例如看書或影片),你至少應該花一到兩倍的時間進行輸出與應用(例如實作或解題)

能做到這樣真的很不簡單,但也只有這樣才能練就真正的能力

0
alincode
iT邦新手 2 級 ‧ 2021-09-27 15:25:42

對於沒有初學的開發者來說
->
對於初學的開發者來說
or
對於沒有經驗的初學開發者來說

我要留言

立即登入留言