c++ - O(1) 表記の数値リストの平均を求める - 定数時間

Question

これが問題です。いくつかの数値で配列を作成するタスクがあります。その後、配列は任意の位置で同じ型の他の数値を受け入れることができます。最終的な配列 (数値が追加されたもの) を取得したら、一定の O(1) 時間で内部の数値の平均を見つける必要があります。それ、どうやったら出来るの？！これが私が例として持っているものです

エレメント: 5 12 7 9 31 平均: 12.8

Answer 1

これが配列クラスの場合、数値が追加および更新されるたびに、すべての数値の合計を追跡できます。次に、すべての更新が完了したら、合計を要素数で割って平均を取得します。合計は事前に計算されているため、平均の計算は O(1) になります。

これが単純に渡される生のメモリ配列である場合、平均を計算するには、すべての数値を合計する必要があります。これは、操作が何であるかに関するセマンティクスゲームを誰かがプレイしていない限り、O(N) です。