

値を中心として, 前後にある数だけ幅を取るために使用できるアルゴリズムがありますか

例えばこの入力で平均値99を基準に, 幅を15とすると

[code]

    98
    174
    58
    49
    78
    90
    75
    170
    
[/code]

下のような結果を期待しています.

[code]

    36-51
    52-67
    68-83
    84-99
    100-115
    116-131
    132-147
    148-163
    164-179
    
[/code]

これは平均値を求め, そこから順に幅を加算していけば求められますが, この手法では基準値より大きい数値と小さい数値で2回のループ処理が必要になります.
これを逐次的, 効率的に行えるアルゴリズムはありますか.

なお, これは度数分布に用いるため, この後に各範囲に収まる数値の数を数え上げます. この背景も含め, より良い手法がございましたら,
ご教授お願い致します.


CC BY-SA 4.0
2020-01-14T15:48:10.707
62243
2020-02-20T00:02:30.277
2020-01-15T05:05:25.750
19110
37457
question
アルゴリズム
値を中心として, 前後にある数だけ幅を取るために使用できるアルゴリズムがありますか


質問者さんの考えてらっしゃるアルゴリズムより飛びぬけて早くなる逐次アルゴリズムは無いと考えて良いです。

まず、入力データである数値列が与えられた時点で、その平均値・最小値・最大値が計算できます。このとき入力データの走査は1回だけです。平均値を知るために必ず1回は走査しないといけないので、これは最小回数です。

そのあと「幅」を計算する訳ですが、小さい方と大きい方でループが2個あるとはいえ、出力されるはずの「幅」たちがちょうど1回ずつ出力されるのみです。ここの計算時間のオーダーは
O(N) であり、O(N²)
ではないことに注意してください（ループがネストしている訳ではありません）。「幅」を全部出力するためには必ず1回は走査しないといけないので、やはり最小回数です。具体的な出力方法によってはほんの少しだけ無駄があるかもしれませんが、ほぼ無駄は無いと考えて良いでしょう。

したがって、質問者さんの考えてらっしゃるアルゴリズムで既に充分効率的です。

ループをひとつにしたいのであれば、最小値 `v` について `平均値 + (幅 + 1) * ((v - 平均値) / (幅 + 1))` ( `/`
は整数の除算) を計算するなどすれば最初の「幅」が分かるので、ここを始点としてループを始めれば良いです。


CC BY-SA 4.0
2020-01-15T05:55:11.490
62252
2020-01-15T05:55:11.490
19110
62243
answer