iT邦幫忙

2025 iThome 鐵人賽

DAY 4
0

「不過你連 Queue 都還沒掌握,就別提 Graph 了。」

「誰說的?我不是已經通過考驗了嗎?」

「通過?那你知道 Queue 的新增和刪除的時間複雜度上限嗎?」

「呃⋯⋯」

「看吧,還差得遠呢!」小孩撇撇嘴,「因為 Queue 的新增和刪除都只會動到頭尾,不需要管中間有多長,所以操作是 O(1)。」

「所以 1 是指 1 秒鐘嗎?」

「不是啦。」小孩笑得像在看笨蛋,「1 代表的是『常數』。簡單來說,不管有多少人排隊,執行這個操作花的時間都是固定的,不會隨著人數增加而變慢。」

「原來如此⋯⋯」我抓了抓頭。

「還有,你之前聽到 O(n) 空間,以為就是 n 倍?」小孩挑眉,「其實可能是 2n 倍、3n 倍,甚至 10n 倍。Big O 的重點是描述『成長趨勢』,不在乎那些常數。這也是為什麼它叫做『複雜度』,因為它不是一個精準的數字。」

「唔,好像有點懂了。」

「懂個鬼啦。」小孩忽然壞笑,「你就沒想過嗎?如果你真的通過考驗,為什麼現在還待在這個世界?」

我心頭一震,「那我剛剛回答的問題不是考驗嗎?」

「那些只是篩選而已,確認你有參加考驗的資格。」小孩的眼神閃閃發亮,語氣像是要宣布什麼恐怖的事:「要知道,真正的考驗,可是要用程式來決勝負的!」

「可是,我還不會寫程式欸!」我慌張地舉手抗議。

小孩眯起眼睛,嘴角勾出一個壞笑:「放心啦,考驗總得有新手福利。我會放點水,只要把我給你的程式碼填完就好。」

他在半空中一揮手,眼前的空間忽然浮現出一段程式碼,字體閃閃發亮:

class Node<T>(val value: T, var next: Node<T>? = null)

class Queue<T> {
    private var head: Node<T>? = null
    private var tail: Node<T>? = null

    fun enqueue(element: T) {
        //todo
    }

    fun dequeue(): T? {
        //todo
    }

    fun peek(): T? = //todo

    fun isEmpty(): Boolean = //todo
}

「這是一段 Kotlin 程式碼,補完這些空格,才算你真正掌握了 Queue!不然的話……就準備一輩子困在這裡,再也喝不到奶茶囉⋯⋯」他笑嘻嘻地說。


上一篇
演算法離不開資料結構
下一篇
程式碼,本來就是給人讀的
系列文
奶茶裡藏的資料結構(Kotlin範例)6
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言