数组函数的时间复杂度

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

不，不是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）。

Answer 2

号码

在索引中以1为增量，您不能期望有比O（n）更好的解决方案。

如果您的算法有效（我不认为它有效），它看起来需要O（n）步骤。

另外，你说你假设数组是排序的，但你还是对它进行了排序。所以你的代码是O（n*log（n））。

更重要的是，尝试对已经排序的数组进行排序是某些排序算法的最坏情况：它甚至可能是O（n**2）。

你在找一个二分搜索法。