iT邦幫忙

2022 iThome 鐵人賽

DAY 2
0
Software Development

刷題也算一種電競吧:演算法與資料結構系列 第 2

Day 1 這到底是什麼符號喔齁齁齁齁齁 - Big O Notation

  • 分享至 

  • xImage
  •  

Big O Notation 是一種表示演算法複雜度的方式。同樣解決一個演算法問題,若該算法執行的時間越少,使用的記憶體愈少,就是越好的解法。可以用來評斷該演算法的好壞。

當我們想要評估一個演算法的複雜度時,我們通常都會假設輸入的資料量趨近無限大,考慮最邊際的情況。

function addUpto(n) {
  let sum = 0;
  for (let i = 0; i <= n; i++) {
    sum += i;
  }
  return sum;
}
function addUpto2(n) {
  return n * (n + 1) / 2;
}

我們看看上面兩個函式,一樣都是從 0 + 1 + 2 +..... 加到輸入的數字,第一個函式的程式碼是一個個慢慢加上去,第二個函式用數學的公式來計算。

我們假設輸入的 n 等於 10 兆,那第一個函式就要跑迴圈 10 兆次,第二個函式依然只要執行那行一次就好。

顯然第二個函式所耗費的時間少很多。

Why use Big O Notation?

若是要單純用時間表示,則會有以下問題:

  1. 不同的電腦,效能也不一樣,同樣的程式跑在效能好的機器上會比較快。
  2. 就算是一樣的電腦,每次執行的時間也會有差異。

那如果換成算有多少步驟呢?

  1. 第一個函式若輸入 10 兆,除去宣告與 return 變數這些固定的步驟,其餘步驟的次數都會隨著輸入的數字而增加,在無限大的情況下,這些零星固定的步驟可忽略不計。
  2. 任何步驟都要一個個計算顯然太過麻煩,倒不如只考慮輸入的參數增長的情況就好。

Fundamental of Big O Notation

第一個函式的需要執行的步驟會依據 n 而越來越多,而不管 3n 還是 10n 個步驟,考慮趨近於無限大的情況下,這些都可以省略成表示 O(n)

第二個函式不管數入多少,都只有幾個步驟而已,而這些也可以省略成表示 O(1)

當我們說到程式複雜度,我們考慮隨著輸入越大越多而時間與記憶體使用的增長趨勢

Performance Trands

演算法效能視覺化工具

tracker

從這網站可以看到,不同演算法在 n 越大的情況下,線的斜率變化。

https://ithelp.ithome.com.tw/upload/images/20240924/201238894rX3W0QagB.jpg

以下舉網站中三個算法為例:

  • addUpToFirst 時間複雜度表示 O(n)
  • addUpToSecond 時間複雜度表示 O(1)
  • countUpAndDown 時間複雜度表示 O(n²),因為迴圈內又有迴圈會是 n * n

不管是 O(5) 還是 O(1000000),他們的斜率都會是一樣的,所以我們在表示上都會簡化成 O(1)

不管是 O(5n) 還是 O(1000n),他們的斜率都會是一樣的,所以我們在表示上都會簡化成 O(n)

不管是 O(n+10) 還是 O(5n+1000),他們的斜率也還是相同,所以我們在表示上會簡化成 O(n)

O(n² + 100n + 500),在 n 無限大的情況下, 100n 相比簡直是小巫見大巫,所以在表示上依然會簡化成 O(n²)

陷阱範例

function logAtLeast5(n) {
  for (let i = 0; i < Math.max(5, n); i++) {
    console.log(i);
  }
function logAtMost5(n) {
  for (let i = 0; i < Math.min(5, n); i++) {
    console.log(i);
  }

上述兩個函式在 n 為無限大的情況下,第一個函式是 O(n),但是第二個函式只要 n 大於 5 就只會執行 5 次,所以第二個函式的複雜度表示 O(1)

Bonus

Big O Notation 表示法的正確發音以 O(n) 為例:歐噢腐恩 (O of n)

而回答時間複雜度部分也可以簡單講 constant time (O(1)) 、 linear time (O(n)) 、 quadratic time (O(n²)) 。


上一篇
Day 0 歡迎來到刷題峽谷 - Algorithms & Data Structures
下一篇
Day 2 哎呀這什麼水平 - 時間與空間複雜度
系列文
刷題也算一種電競吧:演算法與資料結構34
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

2 則留言

1
跑得快
iT邦新手 3 級 ‧ 2022-10-11 14:33:35

到底神摸閃現喔齁齁齁齁齁

抓到動粉/images/emoticon/emoticon01.gif

0
f88083
iT邦新手 4 級 ‧ 2023-10-04 19:28:22

圖片載不出來!是link掛了嗎

感謝提醒 已更新

我要留言

立即登入留言