如何減少陣列的訪問次數

-1

如何降低陣列被訪問的時間量，此刻它訪問陣列的2倍找到用戶提供數字的序列數最多，如何減少陣列的訪問次數

int i=0; 
    int max = -1; 
    int a_i = -1; 

    for (i=0; i<length; i++) 
    { 
    a_i = array(a,i); 

    if (a_i > max) 
    { 
    max = a_i; 
    } 

    return max;

全碼on pastebin

任何幫助表示讚賞。

來源

2012-05-04 UnknownUser

代碼似乎只有一次訪問數組中的每個元素，這是一個爲O（n）的複雜性。如果數組已排序，則可以通過使用二分搜索將複雜度降低到O（logn）。 –

@AdamLiss：好，如果它的排序是O（1），因爲代碼是找到在值的數組中的最大值。但是，這不是OP要求的。說實話，我沒有看到OP是有什麼問題，看代碼（考慮到缺少'}'），我認爲這只是訪問數組一次。 – Skizz

看起來你缺少支撐？ –

簡短的回答

你不能，你必須每個項目迭代，考慮到你有沒有關於陣列信息。

龍答案

你可以在閱讀減少的訪問量，如果你接受失去一些時間

之前使用需要O(n)插入（everyting）的陣列和O(n)找到最低

如果你真的想要的是減少在查找功能花費的時間，你可以使用minimum heap，你會有一些開銷在插入O(n log(n))但你只需要一個O(1)進行搜索。

你也可以搜索之前對數組進行排序，這可能是O(n log n)

來源

2012-05-04 15:57:46 Pierre

如何減少陣列的訪問次數

回答

相關問題