Time/Space-Complexity 方法

Question

我有一个问题要以我们能想到的最复杂的方式回答。

我们得到了一个排序数组 (int) 和 X 值。我们需要做的就是找到数组中有多少个地方等于X值。

这是我对这种情况的解决方案，因为我对复杂性了解不多。我所知道的是更好的方法是没有 for 循环 :X

class Question
{
    public static int mount (int [] a, int x)
    {
        int first=0, last=a.length-1, count=0, pointer=0;
        boolean found=false, finish=false;
        if (x < a[0] || x > a[a.length-1])
                return 0;
        while (! found) **//Searching any place in the array that equals to x value;**
        {
            if ( a[(first+last)/2] > x)
                last = (first+last)/2;
            else if ( a[(first+last)/2] < x)
                first = (first+last)/2;
            else
            {
                pointer = (first+last)/2;
                count = 1;
                found = true; break;
            }
            if (Math.abs(last-first) == 1)
            {
                if (a[first] == x)
                {
                    pointer = first;
                    count = 1;
                    found = true;
                }
                else if (a[last] == x)
                {
                    pointer = last;
                    count = 1;
                    found = true;
                }
                else
                    return 0;
            }
            if (first == last)
            {
                if (a[first] == x)
                {
                    pointer = first;
                    count = 1;
                    found = true; 
                }
                else
                    return 0;
            }
        }
        int backPointer=pointer, forwardPointer=pointer;
        boolean stop1=false, stop2= false;
        while (!finish) **//Counting the number of places the X value is near our pointer.**
        {
            if (backPointer-1 >= 0)
                if (a[backPointer-1] == x)
                {
                    count++;
                    backPointer--;
                }
                else
                    stop1 = true;
            if (forwardPointer+1 <= a.length-1)
                if (a[forwardPointer+1] == x)
                {
                    count++;
                    forwardPointer++;
                }
                else
                    stop2 = true;
            if (stop1 && stop2)
                finish=true;
        }
        return count;
    }
    public static void main (String [] args)
    {
        int [] a = {-25,0,5,11,11,99};
        System.out.println(mount(a, 11));
    }
}

打印命令正确计数并打印“2”。

我只是想知道是否有人可以为这种方法考虑更好的复杂性。

另外，我怎么知道方法的time/space-complexity是什么？

我所知道的关于 time/space-complexity 的是 for 循环是 O(n)。我不知道如何计算我的方法复杂度。

非常感谢！

编辑中： 这是更改后的第二个while循环：

        while (!stop1 || !stop2) //Counting the number of places the X value is near our pointer.
    {
        if (!stop1)
        {
            if ( a[last] == x )
            {
                stop1 = true;
                count += (last-pointer);
            }
            else if ( a[(last+forwardPointer)/2] == x )
            {
                if (last-forwardPointer == 1)
                {
                    stop1 = true;
                    count += (forwardPointer-pointer);
                }
                else
                    forwardPointer = (last + forwardPointer) / 2;
            }
            else
                last = ((last + forwardPointer) / 2) - 1;
        }
        if (!stop2)
        {
            if (a[first] == x)
            {
                stop2 = true;
                count += (pointer - first);
            }
            else if ( a[(first+backPointer)/2] == x )
            {
                if (backPointer - first == 1)
                {
                    stop2 = true;
                    count += (pointer-backPointer);
                }
                else
                    backPointer = (first + backPointer) / 2;
            }
            else
                first = ((first + backPointer) / 2) + 1;
        }
    }

您如何看待这种变化？我认为这会将时间复杂度更改为 O(long(n)).

Answer 1

首先让我们检查一下您的代码：

代码可以进行大量重构和清理（这也将导致更有效的实施，但没有改进时间或 space 复杂性），但算法本身还不错

它的作用是使用标准二分搜索查找具有所需值的项目，然后扫描到后面和前面以查找所有其他出现的值。

在时间复杂度上，该算法为O(N)。最坏的情况是整个数组都是相同的值，而你最终在第二阶段迭代了所有数组（二分查找只需要 1 次迭代）。 Space 复杂度为 O(1)。内存使用量 (space) 不受输入大小增长的影响。

如果您继续在 2 sub-arrays（前后）上使用二进制搜索并以这种方式以对数方式增加 "match range"，则可以改善最坏情况下的时间复杂度。时间复杂度会变成O(log(N))。 Space 复杂度将保持 O(1)，原因与之前相同。

但是，real-world 场景（其中数组包含各种值）的平均复杂度将非常接近，甚至可能倾向于您自己的版本。

Time/Space-Complexity 方法

Time/Space-Complexity method

time-complexity

space-complexity