如何在子線性時間中從行主陣列中選擇列？

可以說我得到了一排主陣列。如何在子線性時間中從行主陣列中選擇列？

int* a = (int *)malloc(9 x 9 x sizeof(int));

看這個作爲2D 9x9的陣列，其中一個（行，列）索引對應於[行* 9 +柱] 有一種方法在那裏我可以從該陣列中的子選擇的單個列線性時間？由於列不會是連續的，我們不能像我們做直接memcpy來獲得單行。

線性時間解決方案將是顯而易見的，但我希望有一些亞線性解決方案。

謝謝。

來源

2012-03-02 smhx

只是爲了讓我清楚我的問題。對於複製單獨的行，如果使用memcpy，由於內存是連續的，並且如果數組足夠大，它將逐塊複製，而不是線性迭代每個元素，因此我說，行復制是次級複製，線性的。 – smhx 2012-03-02 17:31:32

和次線性，我的意思是比O（N）更快的解決方案，其中N是方陣的寬度。 – smhx 2012-03-02 17:32:22

目前尚不清楚你的意思是次線性。如果將2D陣列視爲NxN尺寸，那麼次線性對否是不可能。要複製否您需要執行的元素否複製操作，副本將是線性上正在複製的元素數量。

註釋約memcpy似乎表明，你誤認爲是memcpy次線性上元素的數量被複制。不是這樣。 memcpy的優點是隱藏在big-O表示法中的常量很小，但是對被複制的內存大小的操作是線性的。

接下來的問題是大O分析是否真的有意義。如果您的數組是9x9，那麼隱藏在大O符號的常量中的效果可能比複雜性更重要。

來源

2012-03-02 17:14:51

一次不復制一個塊，這使得它比線性複製每個元素更快。 – smhx 2012-03-02 17:29:08

@nicko，複製塊也是線性操作。無論如何，O（n/blocksize）仍然是O（n）。 – 2012-03-02 17:31:23

如果塊大小是sqrt（N），那麼操作不會變成O（N^1/2）？ – smhx 2012-03-02 17:35:34

我真的不明白你的意思，但是考慮：

const size_t x_sz=9; 
size_t x=3, y=6; //or which ever element you wish to access 
int value=a[Y*x_sz+x];

這將是一個常數時間O（1）表達。它必須計算偏移量並加載該值。

通過的每一個值在一列迭代：

const size_t x_sz=9, y_sz=9; 
size_t x=3; //or which ever column you wish to access 

for(size_t y=0; y!=y_sz; ++y){ 
    int value=a[Y*x_sz+x]; 
    //value is current column value 
}

再次每次迭代一定的時間，整個迭代序列因此是O（n）（線性），請注意，也仍然如果它是線性的是連續的。

來源

2012-03-02 17:14:10 111111

如何在子線性時間中從行主陣列中選擇列？

回答

相關問題