在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'所以如果數組的開始地址是已知的'我們如何知道數組的起始地址？我們只給'A [4]'來訪問第四個元素。 – Amar

-1

正如@Nullman在評論中所說的，並且至少在引用Python時，在O（1）中訪問list。

來源：https://wiki.python.org/moin/TimeComplexity

來源

2017-02-24 14:09:47 Adirio

索引爲O的陣列（1）是可能的，因爲計算訪問要在一個步驟中完成的數據。

這是如何做的很簡單，比如說你創建一個10個整數的數組。

int[] intArray = new int[10];

這裏發生的事情是，你所要求的內存塊大到足以容納10個整數（在Java中，他們是32位的，所以10個* 4字節）。

當內存被保留時，該塊開始處的內存地址被返回並放入intArray變量（包含地址/變量的變量被稱爲指針）。

爲了讓這個更容易理解，你可以將內存（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

的例子。在這種情況下startAddress在charArray值，指數是每個元素數字1和大小是個體炭（1個字節）的大小，以便它使我們的8的存儲器地址

來源

2017-02-24 14:29:44

'當內存被保留時，該塊開始處的內存地址被放回到intArray變量中（一個包含地址/變量的變量稱爲指針）。「需要引用這個。 – Amar

在o（1）中訪問數組的第n個索引

回答

相關問題