o（1）の配列のn番目のインデックスへのアクセス

-2

非常に基本的な質問で、O（1）コストでn番目のインデックスに直接アクセスする方法は？配列を初期化するとき、各索引のアドレスを保持するためのデータ構造が構築されていますか（後でo（1）コストにアクセスするには）？さもなければ配列の最初のインデックスからn番目のインデックスまで移動しなければなりません。 o（1）で配列要素にアクセスする理由は何ですか？o（1）の配列のn番目のインデックスへのアクセス

出典

2017-02-24 Amar

uhh、配列はO（1）でアクセスする構造体です。リンクされたリストを考えています – Nullman

これは通常、配列を連続したメモリに格納することによって行われます。したがって、配列の開始アドレスが分かっている場合、マシンは開始アドレスに適切な量を追加することによって、それ以上の位置のアドレスを見つけることができます。そのため、配列アクセスはO（1）であり、（たとえば）リンクリストアクセスはそうではありません。 – khelwood

@khelwood '配列の開始アドレスがわかっているなら'配列の開始アドレスはどうやって知っていますか？ 4番目の要素にアクセスするために 'A [4] 'を与えます。 – Amar

-1

@Nullmanがコメントで述べたように、少なくともPythonを参照するときは、listはO（1）でアクセスされます。

出典：必要なデータにアクセスするための計算は、1つのステップで行われるため、https://wiki.python.org/moin/TimeComplexity

出典

2017-02-24 14:09:47 Adirio

はOで配列のインデックス作成は、（1）が可能です。

これは非常に簡単です。たとえば、10個の整数の配列を作成するとします。

int[] intArray = new int[10];

は何ここで起こっていることは、あなたが（Javaでは、彼らは32ビットなので、10 * 4バイトの長さである）10個の整数を格納するのに十分な大きさのメモリのブロックを求めているということです。

メモリが予約されると、このブロックの先頭のメモリアドレスが返され、intArray変数に格納されます（アドレス/参照を含む変数はポインタと呼ばれます）。

これを分かりやすくするために、それぞれがアドレスを持つ1バイトブロックの長いリストとしてピクチャメモリ（RAM）を描画することができます。

Data: [ 00000000 ] [ 11111111 ] [ 00001111 ] 
Address:  7    8   9

あなたは、配列の一部へのアクセスを得るためにインデックスを使用する場合、何が起きていることは、インデックスを使用すると、その場で必要ブロックのメモリアドレスをcalcuateするために使用されていることです。

この場合

char[] charArray = new char[3]; // This returns memory address 7 

charArray[1] = 'b'; // Here the memory address is calcuated with the formula 
       // startAddress + index * Size Per Element

上記の例を使用して、開始アドレスがcharArrayの値であり、インデックスは要素ごと番号1およびサイズである個別CHAR（1バイト）のサイズであるので、それは私達に8のメモリアドレスを与えます

出典

2017-02-24 14:29:44

'メモリが予約されると、このブロックの先頭のメモリアドレスが返され、intArray変数に格納されます（アドレス/参照を含む変数はポインタと呼ばれます）。 – Amar

o（1）の配列のn番目のインデックスへのアクセス

答えて

関連する問題