java - 数组插入的时间复杂度

Question

我正在编写函数来查找目标值应插入给定数组的位置。我们假设数组具有不同的值并且按升序排序。

这里我希望时间复杂度为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) 中。

Answer 1

没有。

该代码迭代(最坏情况)数组中的所有值。如果随机插入值，插入点将平均位于数组的中间。正如 @LukeLee 指出的那样，当您找到位置时，您不会打破循环，因此您将始终迭代每个可能的位置 - 所有 N 个位置。

为了获得 O(logN) 性能，您必须跳过大量比较。查看binary search,如果你的数组是有序的。