申論題 - 阿摩線上測驗

申論題資訊

試卷：100年 - 100年升官等、關務人員升官等考薦任資料結構#45297
科目：公職◆資料結構
年份：100年
排序：0

一、複雜度big-Oh O的定義為：f(n) = O(g(n)) 若且唯若存在一實數c＞0 和一整數n0＞0，使得對所有整數n≧n₀，f(n) ≦ cg(n)皆成立。假設有如下的程式：

設敘述 2 執行一次需 1 個單位時間，敘述 3 執行一次需 1 個單位時間，敘述 4 執行一次需 2 個單位時間，敘述 5 執行一次需 3 個單位時間，敘述 6 執行一次需 2 個單位時間，敘述 7 執行一次需 1 個單位時間。

⑵此程式之時間複雜度（time complexity）為何？以 big-Oh 表示之，並請用上述的定義證明答案的正確性。（註：無證明者此小題不給分。）（10 分）