申論題 - 阿摩線上測驗

申論題資訊

試卷：111年 - 111 身心障礙特種考試_三等_資訊處理：資料結構#107534
科目：公職◆資料結構
年份：111年
排序：0

題組內容

一、請回答下列 Big O 的相關問題：

申論題內容

(一) Big O Notation，根據維基百科又稱為漸進符號，它是用於描述演算法漸進行為的數學符號。更確切地說，它用更簡單的函式來描述一個演算法在數量上的漸進趨勢。某個問題可採用 5 個演算法 A～E 求解，各演算法執行時間的 Big O 分別如下：A 為 O（N²），B 為 O（Nlog（log N）），C 為 O（），D 為 O（N²log（N）），E 為 O（SQRT（N））。當 N 很大時，請根據演算法的執行時間，由慢至快排序這 5 個演算法。（10 分）

詳解 (共 1 筆)

詳解提供者：WJ

E為O(N^0.5) 肯定最快
先排序ABCD
A、D都至少在O(N²) 其中D又多了logN 所以D比A慢
B、C很明顯不到N²的程度
B跟C比較的話
先共除以N，剩下log(logN)與N^0.5比較
而當N很大的時候，後者會比較慢
所以C比B慢

所以由慢到快排序為
D A C B E