首页 > 資料結構筆記(一):演算法、時間複雜度、空間複雜度

資料結構筆記(一):演算法、時間複雜度、空間複雜度

互联网 2021-07-24 09:34:54
程式  演算法  資料結構  C 語言 資料結構筆記(一):演算法、時間複雜度、空間複雜度

資料結構,據說要學好程式只要學好資料結構和演算法就好了。但這明明是資料結構筆記啊,怎麼會提到時間複雜度呢?我也不知道,第一章就從時間複雜度和空間複雜度開始吧 XD

Noob TsaiNoob TsaiNov 7 2016• 4 min read資料結構筆記(一):演算法、時間複雜度、空間複雜度

資料結構,據說要學好程式只要學好資料結構和演算法就好了。但這明明是資料結構筆記啊,怎麼會提到時間複雜度呢?我也不知道,第一章就從時間複雜度和空間複雜度開始吧 XD

ds

演算法由三個部分組成:輸入、計算步驟、輸出,它是明確的、有限的、且有效率的。

註:演算法並不等於寫程式。一個演算法除了可以虛擬碼或程式碼來記載,並編譯成電腦程式;也可以流程圖來記載,並設計成電子電路。

而要評論一個演算法的好壞,最基本的方式就是計算它所使用的時間和空間。

但一個演算法在不同效能的電腦上跑,可能會有不同的情況。所以我們用複雜度的方式來描述一算法的趨勢。簡單來說就是用比較科學的方法來描述演算法的可能複雜情況。

時間複雜度

一個程式的時間複雜度是指完全地執行程式所需的計算機時間。

如果一個演算法執行的步驟是固定的,無關輸入的值而改變,那我們會記成 $O(1)$,例如:

function(int n){print(n);}

不管 n 輸入多少,這個程式永遠只會執行一次。

而下面這個演算法:

function(int n){for(i=0;i
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。