私は今年 AP コンピューター サイエンス試験を受けましたが、問題の 1 つである 16 番の問題は、実際には完全に正解ではないように見えました (ただし、AP の人々がどちらの答えを正解として意図していたかは明らかでした)。
質問は次のとおりでした。
次のうち、降順でソートされた配列では、ソートされていない配列よりも効率的に実装できないものはどれですか?
A.) 要素の検索
B.) 中央値を見つける
C.) 算術平均を求める
D.) 昇順で出力する
E.) 最大値を見つける
単純に答え C を付ける人もいますが、その答えが完全に正しいわけではないことは確かです。
この例を見てみましょう: 4503599627370496 個の倍精度浮動小数点値を含む配列があり、そのうちの 1 つは 9007199254740993 に等しく、残りはすべて .999999 です。大きな値が正確にどこにあるかに応じて、平均を見つける単純な方法 (要素を繰り返し、それらを合計し、合計をカウントで割る) は、(1) 大きな要素が後で合計に追加されない限り、正しい値を生成しません。 (つまり、配列がソートされている)、(2) より高い精度の値を使用して合計を追跡する (つまり、より多くのリソースを使用する)、または (3) より多くのリソースを必要とする他の方法を使用する。
そして、より多くのリソースを必要とする場合、定義上、効率が低下します。
また、これはかなり要点を避けていますが、コンピューティングの標準モデルに自分自身を制限しない場合 (たとえば、量子コンピューターを許可する場合)、それらのいずれも、並べ替えられていない配列で効率的になるということです。ソートされた配列。
試験問題に実際に欠陥があるのでしょうか、それともここで何かを見逃したのでしょうか?