java - 数组函数的时间复杂度

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 .