計算量から処理時間を見積もる
T社の重複チェックのプログラムは、データ件数nに対して計算量がO(n^2)のアルゴリズムで書かれている。1,000件の処理に2秒かかったとき、同じ環境で3,000件を処理するのにかかる時間はおよそどれか。処理時間は計算量に比例するものとする。
- A
約6秒
- B
約7秒
- C
約18秒
- D
約54秒
正解と解説を見る
正解:C
計算量O(n^2)は、件数が k 倍になると処理量が k^2 倍になる。件数が増えると処理時間が急に伸びるため、大量データでは計算量の小さいアルゴリズムを選ぶことが重要になる。
- A
誤り。件数が3倍で時間も3倍としており、O(n)の場合の計算になっている。
- B
誤り。O(n log n)の場合のおよその見積もりで、O(n^2)には当てはまらない。
- C
正しい。件数が3倍になると、O(n^2)では処理量が3^2=9倍になるので、2秒×9=18秒。
- D
誤り。3^3=27倍としており、O(n^3)の場合の計算になっている。
このサイトの問題は、各試験の公開されている出題範囲に沿って作ったオリジナルの模擬問題です。本試験の問題ではありません。一般社団法人データサイエンティスト協会・一般財団法人統計質保証推進協会の公式サービスではありません。