「不過你連 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!不然的話……就準備一輩子困在這裡,再也喝不到奶茶囉⋯⋯」他笑嘻嘻地說。