2021年5月4日

從找衣服了解時間複雜度(Time Complexity)

剛剛用日常上班前挑衣服的例子和沒學過程式的 00 說明時間複雜度的概念很好理解耶~!
例子是這樣的...
一早要出門的時候,想要從衣櫃中找出紅色的上衣。
其中一種方式是像左圖一樣,這是掏寶上很熱門的「疊衣服褲子收納神器」,雖然看起來整理的很乾淨,但如果你要從中找到紅色的衣服,你就得要由上而下一件一件找,最糟的情況就是一直翻到最下面才能找到你要的紅色衣服。
另一種方式是像右圖一樣,把衣服用立起來的方式,一眼就可以看到紅色的衣服在哪,直接拿出來,幾乎不用找。
左圖的那種方式,時間複雜的就是 O(n),n 就是衣服的件數,雖然紅色的衣服有可能就放在最上面,一眼就可以看到,但在探討時間複雜度的時候都要考慮最差的情況,所以如果你有 n 件衣服,最差的情況就是要把 n 件衣服都翻過才會找到紅色那件。
右圖的方式它的時間複雜度是 O(1),在你沒有忘記其實衣服已經被丟到洗衣籃的前提下,你看一眼,翻都不用翻就可以把紅衣服直接取出(請先忽略掉人腦內建的視覺搜尋系統,那是另一個有趣的故事 XD)。這種不用一個一個找,就直接取出的,時間複雜度就是 O(1)
有了這個時間複雜度的概念後,是不是覺得左邊的那個商品實用性沒這麼高啦~ XDD
但我還是附一下購物連結(誤)
真的是沒想到學演算法還可以用在購物吧!

圖片來源