iT邦幫忙

2021 iThome 鐵人賽

DAY 1
2
自我挑戰組

一個月的演算法挑戰系列 第 1

Day01:時間複雜度

剛開始,我想說點什麼

看過市面上許多解釋演算法的資料,有些書搭配圖片,有些影片淺顯易懂,為了挑戰自己以及將演算法了解透測,開始了這次的鐵人賽。

開始的時候,想要推薦一本書給大家,是這本書引我進入演算法之門(笑)

**演算法圖鑑:26種演算法 + 7種資料結構,人工智慧、數據分析、邏輯思考的原理和應用全圖解
**

身為一個半路轉職的的工程師,發現在軟體的領域,徹底實現「活到老,學到老」的精神,以此為基礎,開始這30天的訓練吧!

演算法是什麼

演算法,可以簡單說也可以很複雜的講。簡單來說,是一個解決問題,並且用來達到目的方法,換句話說,輸入 + 演算法 = 輸出。而衡量此種方法是否為最有效方式,就可以利用時間或空間複雜度來測量。

時間複雜度 Time complexity

此處的時間,指的不是程式執行時所計算的秒數,而是從程式執行的第一步到完成,中間的步數。換句話,就是輸入內容到輸出答案之間的時間。
在表示時間複雜度時,會使用Big O(念作order),下圖是幾種常見的表示方式

  1. O(1):陣列讀取
  2. O(n):無序陣列的搜尋
  3. O(log n):二分搜尋
  4. O(n log n):合併排序,最快的比較排序
  5. O(n²):泡沫排序、插入排序
  6. O(2^n):費波那契數列

執行效率:

O(1) < O(log(n)) < O(n) < O(n*log(n)) < O(n^2) < O(n^3) < O(2^n) < O(n!)

#copy 時間複雜度為O(1),僅執行一次即可達成目的
x = ["Hello World"]
y = x.copy()
print(y)

Python官網也有貼心提供不同方法之間的時間複雜度,有興趣延伸閱讀的人可以參考一下。

https://wiki.python.org/moin/TimeComplexity


下一篇
Day02:空間複雜度
系列文
一個月的演算法挑戰30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言