高速列ごとの合計。可能？

は、この絵を見てください：高速列ごとの合計。可能？

enter image description here

は速くはO（n^2）に比べてすべての列ごとの列の合計を見つけることが、それは可能ですか？

：私たちは、この（そして、2行を残り、一度に2行を合計した後、残りの2行に...）のような集計を再編成する場合

は、まず私は、それはそれのn *ログ（n）を作ることが可能だと思いました

enter image description here

しかし、私はプラスの数を数え、どちらの場合も7 = 7となり、両方の写真から7となりました。

このような合計をn * log（n）の時間で構成することは可能ですか、私は自分自身をだましてしまっています（FHTやFFTのような変換があるので、そうかもしれません）。

2012-03-28 Vadim

nとは私はあなたに 'n = 8'と' m = 10'を意味し、あなたは '（n-1）* m'プラスを持っています – hroptatyr

@hroptatyr：私は別のnとmを描いていますが、n^2とn * log （n）単純化のために。しかし、例えばn = m = 8と仮定しても差はありません。 – Vadim

@hroptatyr：nは行数です。 m - 列の数 – Vadim

であり、私たちの入力サイズはO(n^2)なので、私たちのアルゴリズムはそれより速くなることはできません（すべての入力値を使用しているため）。

これは、nが行の量であり、行列が正方形であることを前提としており（n^2）、要素間に特別な関係はありません。

2012-03-28 10:39:29 orlp

@amit：各配列が標本化された正弦波を表すことが分かっていれば、何か変わるでしょうか？（しかし、それらの和は周期的な波形ではないので、FFTは使用できません） – Vadim

@Vadim：すべての値が0-1の範囲にあります。 – orlp

いいえ（少なくとも）O（n^2）時間かかるメモリからn^2個のアイテムを読み込む必要があります。

_{1と仮定すると、Nは列数（または列数）です。}

2012-03-28 10:38:59

マトリクスに関する詳しい知識がある場合を除き、O(n^2)の方がよくできません。

あなたは、あなたのアイデアがあるためにも、最初の反復で、O(n^2)であることに注意してください、あなたはまた、Omega(n^2)

の下限を取得するので、各カラムの正しい合計を取得するために行列の各要素を読み取る必要があります、入力した値がO(n^2)

2012-03-28 10:39:11 amit

答えて