身心障礙人員考試身障四等-資訊處理類科計算機概要115 年第 15 題單選題
複雜度（complexity）等級函數用來大致估算演算法效率。當輸入資料大小為 n，某演算法的複雜度為 f(n)，當 n 足夠大，f(n) 的上限都一定不超過或等於 g(n) 的某常數倍，我們可以說 f(n) 複雜度為 O(g) 等級。下列何者邏輯上正確定義 O()？（∃ 為"存在一個或一個以上"，∀ 為"對每一個都要求成立"）
A{f∣∃c1,c2,∃k,∀x>k:∣c1g(x)∣≤∣f(x)∣≤∣c2g(x)∣}
B{f∣∃c,∃k,∀x>k:∣f(x)∣≤∣cg(x)∣}正確答案
C{f∣∃c,∀k,∀x>k:∣f(x)∣<∣cg(x)∣}
D{f∣∀c,∀k,∀x>k:∣cg(x)∣<∣f(x)∣}
B正確答案
Big-O 符號 O(g) 的定義為存在常數 c 與 k，使得當 x>k 時，∣f(x)∣≤∣cg(x)∣。
為什麼答案是 B
正確描述 Big-O O(g) 的定義，表示函數的漸進上界。
考點：Big-Theta考點：Big-O考點：邏輯量詞
