演算法中關於時間複雜度分析的敘述：若 n 為輸入大小，則下列何者正確？
A一個 O(n²) 的時間演算法一定比 O(n) 時間演算法快
B若不說明，演算法的時間複雜度通常指該演算法最糟執行狀況下的情形正確答案
C一個最佳執行時間為 20 秒且最糟執行時間為 100 秒的演算法的平均執行時間為 60 秒
D任何排序演算法的時間複雜度不可能為 O(n)
答案與詳解
逐選項解析
A一個 O(n²) 的時間演算法一定比 O(n) 時間演算法快✕ 錯誤
大 O 符號描述的是輸入規模 n 趨近無限大時的漸近行為。當 n 較小或常數項較大時，O(n²) 的演算法實際執行時間可能比 O(n) 短，因此並非一定較快。
B若不說明，演算法的時間複雜度通常指該演算法最糟執行狀況下的情形✓ 正確
在演算法分析中，若未特別標明是最佳或平均情況，時間複雜度預設指最壞情況（Worst-case），以確保演算法在任何輸入下都不會超過此時間上界。
C一個最佳執行時間為 20 秒且最糟執行時間為 100 秒的演算法的平均執行時間為 60 秒✕ 錯誤
D任何排序演算法的時間複雜度不可能為 O(n)✕ 錯誤
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
立即註冊觀看完整詳解 已有帳號?登入
