Q&A
普通に考えてみればいいのでは？
疑問
例えば３次元配列Aがあるとして、A[i][j][k]へのアクセスはO(3)？それともo(1)?
普通に考えると、「３次元配列Aのi番目の配列の中のj番目の配列の中のk番目」でO(1 * 3)で、実際一次元の配列のアクセスより遅いことが確認できているのですが、このテーマについて言及されているソースや記事がぱっと見で見つからなかったので、詳しい説明ができる人がいないかと思い投稿してみました。
現状ではO(n)表記の理解が間違っているので、O(n)表記を使って質問したいのなら、正しく理解しましょう。
O(n)表記を使わないで知りたいことを質問できるなら、そちらの方が良いと思います。
タイトルで
> n元配列へのアクセスはO(n) ?
という問いをしているので
Aが3次元配列の時の A[0][0][0]
Aが4次元配列の時の A[0][0][0][0]
Aが5次元配列の時の A[0][0][0][0][0]
:
:
Aがn次元配列の時の A[0][0][0][0][0]……[0]
:
となった時の必要な計算時間の話をしていることになるのですが、それで合っているんでしょうか??
もし、
n元配列へのアクセスはO(n) なのであれば、3次元配列ならO(3)なんでしょうか?
というのが質問の主旨なのだとしたら、otn さんが"O(n)表記の理解が間違っている"と指摘したのが合ってますね。
メモリアクセスについてランダウの記法による計算量を考えることには意味がありません。
回答3件
0
そもそも論として、O(3)とO(1)は同じ意味です（通常O(1)と書きます）。
定数倍の差は、ランダウ記号では無視されます。
投稿2021/08/10 12:53
編集2021/08/10 12:54
総合スコア145208
0
単純に次元ごとに順に並んだメモリ配置を考えるなら、O(n)でしょうね。
次元が増えるごとに比例してメモリ番地を求めるための乗算・加算の回数が増えます。
A[i] : i
A[i][j] : i*width+j
A[i][j][k] : i*(width*height)+j*width+k
と言った具合に。
改めて考えてみると、質問の解釈の仕方が2通りあると思いました。
- nを変数として「n元配列へのアクセス」という1つの対象に対してのオーダーを質問している。
「例えば３次元配列Aがあるとして～」は、質問を分かりやすくするための解説。(オーダーの理解は間違っている)
2. nを固定した複数の「○元配列」についてそれぞれのオーダーを質問している。
「例えば３次元配列Aがあるとして～」は、質問の対象のうち1つを抜き出したもの。
自分は前者の解釈でO(n)と言っていましたが、後者の解釈では「どの定数nについても、O(1)」が答えとなります。
投稿2021/08/08 14:11
編集2021/08/11 04:41
総合スコア3047
0
ベストアンサー
趣味でやっているので間違っている可能性もありますが、それでもいいなら。
恐らく今回はオーダー記法で書くとO(1)だと思います。
そもそも計算量には二種類あり、
時間計算量と空間計算量があります。
オーダー記法で表現されるのは時間計算量の方っぽいです。
この時間計算量は極端なことをいえば『最悪かかる時間』です。
配列の要素数がNあって、O(N)であれば、最悪時にはN回は計算することになります。
ですが、厳密には『かかる時間』ではなく、『データ量が増えるとどのぐらい処理時間がかかるか』だったはずです。
二次関数の方だっかな？ あるいは比例・反比例の関係とかですね。
もしO(N)で、N = 10`, N = 20, N = 30 … と考えると、比例していますね。
O(N^2) であれば…とかんがえてみてください。
ヒント：参考
そう考えると、二次元配列だろうと三次元配列だろうと、for文を使っての探索とかでなくランダムアクセス(直接アクセスする方法)であれば、変動なしなのでO(1)になるのではないかと思いますが。
投稿2021/08/08 10:29
総合スコア4958
あなたの回答
tips
プレビュー
