Hsin-Yu (Bryce) Huang
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))

若有錯誤請不吝指教

--

--

Hsin-Yu (Bryce) Huang

Software Engineer | Web Development | Information Security