數組函數的時間複雜度

Question

我寫了一個函數來查找目標值應該插入到給定數組中的位置。我們假設數組具有不同的值並按升序排序。我的解決方案必須在O（log N）時間複雜度

public static int FindPosition(int[] A, int target) { 


    int a = A.length/2; 
    System.out.println(a); 
    int count = a; 
    for (int i = a; i < A.length && A[i] < target; i++) { 
     count++; 
    } 
    for (int i = a; i > A.length && A[i] > target; i--) { 
     count++; 
    } 
    return count; 
} 

此代碼是否具有O（log N）的複雜性？

Answer 1

簡短的回答

號

再回應

隨着你的指數1的增量，你不能指望有比O(n)一個更好的解決方案。

如果你的算法可以工作（我不這麼認爲），它看起來好像需要O(n)步驟。

另外，你說你認爲數組是排序的，但是你仍然要對它進行排序。所以你的代碼是O(n*log(n))。

更重要的是，嘗試對已排序的數組進行排序是某些排序算法的最壞情況：它甚至可能是O(n**2)。

您正在查找binary search。

Answer 2

不，它不是nlogn

public static int FindPosition(int[] A, int target){ 
/* 
Time taken to sort these elements would depend on how 
sort function is implemented in java. Arrays.sort has average 
time complexity of Ω(n log n), and worst case of O(n^2) 
*/ 
Arrays.sort(A); 


/*Time taken to run this loop = O(length of A) or O(N) 
where N = arraylength 
*/ 

for(int i=a;i<A.length&&A[i]<target;i++){ 
    count++; 
} 
/*Time taken to run this loop = O(length of A) or O(N) 
where N = arraylength 
*/ 
for(int i=a;i>A.length&&A[i]>target;i--){ 
    count++; 
} 
return count; 
} 

現在的時間複雜度會由最長的三個以上的表示，因爲分配和所有人都在固定時間內完成的。

因此，在最壞的情況下使你的複雜度爲O（n^2）。