3 min readApr 27, 2020
文中提到用unshift實作enqueue,功能雖能達到FIFO,但時間複雜度卻不合標準,因為unshift的time complexity實為O(N)而非O(1)。
可以透過下面這個簡易的測試,實際跑完以後會發現,兩次執行unshift的時間並非同一個數量級(我自己實測平均約是7ms vs 39ms)。
這個測試的結果,暗示unshift插入一個element所消耗的時間會隨著Queue內element數量改變,因此unshift的Time complexity非O(1)。(要證明是O(N)請自行設計實驗囉)
// --------------------[First try]--------------------
// Create a queue with O(N) elements
var queue = [];
for (var i = 0; i < 10000000; i++) queue.push(1);// Test unshift Time Complexity
var start = new Date().getTime();
queue.unshift(2)
var end = new Date().getTime();
console.log(end - start);// --------------------[Second try]--------------------
// Create a queue with O(N*10) elements
var queue = [];
for (var i = 0; i < 100000000; i++) queue.push(1);// Test unshift Time Complexity
var start = new Date().getTime();
queue.unshift(2)
var end = new Date().getTime();
console.log(end - start);
若enqueue的time complexity為O(N), 那其實也不算Queue了
附上Queue的定義(擷取自https://en.wikipedia.org/wiki/Queue_(abstract_data_type))
若有錯誤請不吝指教