民國108年 第2梯次 電腦軟體設計(JAVA)乙級 學科

第78題

下列演算法之時間複雜度,那些敘述是正確的?

題目

下列演算法之時間複雜度,那些敘述是正確的?

  1. (1) 若資料量n 為4096,演算法之計算時間為512m s;當資料量n 增加至16384 時,此演算法之計算時間需2048ms。我們可推論該演算法之時間複雜度為O(n)
  2. (2) 若資料量n 為4096,演算法之計算時間為512ms;當資料量n 增加至16384 時,此演算法之計算時間需8192ms。我們可推論該演算法之時間複雜度為O(n log n)
  3. (3) 若資料量n 為4096, 演算法之計算時間為512ms;當資料量n 增加至16384 時,此演算法之計算時間需1024ms。我們可推論該演算法之時間複雜度為O(n ) 或 O(log n)
  4. (4) 若資料量n 為4096,演算法之計算時間為512ms;當資料量n 增加至16384 時,此演算法之計算時間需4096ms。我們可推論該演算法之時間複雜度為O(n 2)

官方答案

(1) 若資料量n 為4096,演算法之計算時間為512m s;當資料量n 增加至16384 時,此演算法之計算時間需2048ms。我們可推論該演算法之時間複雜度為O(n)、(3) 若資料量n 為4096, 演算法之計算時間為512ms;當資料量n 增加至16384 時,此演算法之計算時間需1024ms。我們可推論該演算法之時間複雜度為O(n ) 或 O(log n)

官方資料