數組插入的時間複雜性

我正在寫函數來查找目標值應插入給定數組中的位置。我們假設數組具有不同的值並按升序排序。數組插入的時間複雜性

這裏我想要的時間複雜度是O（logN）。

public static int FindPosition(int[] Arr, int element) 
{ 
    int i; int u=0; 
    { 
     for(i=0;i<Arr.length;i++) 
     { 
      if(element>Arr[i]) 
      u++; 
     } 
    } 
    return u; 
}

這個程序是否具有O（log n）的時間複雜度。任何人都可以幫助我改變功能，所以它可以在o（log n）中。

來源

2017-04-20 user7799918

這是O（n）。你想要二進制搜索。這是線性搜索。一旦元素<= Arr [i]，你可以停止循環。 –

假設你引用這個[post]（http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it）來理解如何計算時間複雜度。 –

第

該代碼對數組中的所有值進行迭代（最壞情況）。如果值是隨機插入的，插入點將平均爲數組的中間位置。 @LukeLee指出，當你找到位置時，你不需要循環break，所以你總是會遍歷每一個可能的位置 - 全部N位。

爲了獲得O（logN）性能，您將不得不跳過很多比較。如果您的數組已訂購，請查看binary search,。

來源

2017-04-20 00:57:39

不幸的是，不管代碼如何，代碼都會遍歷所有元素。 –

Egad，你說得對。更新。 –

數組插入的時間複雜性

回答

相關問題