申論題 - 阿摩線上測驗

申論題資訊

試卷：111年 - 111 地方政府特種考試_三等_統計：資料處理#112507
科目：資料處理
年份：111年
排序：0

三、若某一個檔案有1024筆紀錄，每一筆紀錄的存取時間為10^-3秒，分別使用線性搜尋法及二分搜尋法進行資料搜尋。求兩種搜尋法各自平均所需花費的時間？以及時間相差大約多少倍？

詳解提供者：114年高考上榜

假設搜尋一筆資料的時間複雜度分別為 O(1) 和 O(log n)，其中 n = 1024 為資料筆數，線性搜尋法平均需要搜尋 n/2 = 512 次，二分搜尋法平均需要搜尋 log2 n ≈ 10 次。

因此，線性搜尋法平均所需時間為：

T1 = (n/2) × 10-3 = 512 × 10-3 秒 = 0.512 秒

二分搜尋法平均所需時間為：

T2 = log2 n × 10-3 ≈ 10 × 10-3 秒 = 0.01 秒

兩種搜尋法所需時間相差 T1/T2 ≈ 51.2 倍，可以看出二分搜尋法的效率遠高於線性搜尋法。