Big-Oh符号表示单个while循环覆盖带有两个迭代器变量的数组的两半

Question

试图通过我的Big-O理解进行测试(显然需要一个非常基本的Big-O理解)我已经出现并在我的书中做了一些练习问题.

他们给了我以下片段

public static void swap(int[] a)
{
    int i = 0;
    int j = a.length-1;

    while (i < j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        i++;
        j--;
    }
}

我觉得很容易理解.它有两个迭代器,每个迭代器覆盖一半的数组,并且有一定量的工作(我认为它们都是O(n/2))

因此O(n/2)+ O(n/2)= O(2n/2)= O(n)

现在请原谅,因为这是我目前的理解,这是我尝试解决问题的方法.我发现了许多big-o online的例子,但没有一个像这样,迭代器基本上同时增加和修改数组.

它有一个循环的事实让我觉得它是O(n)无论如何.

有人会介意为我清理这个吗？

谢谢

Answer 1

它有一个循环的事实让我觉得它是O(n)无论如何.

这是对的.不是因为它正在形成一个循环,而是因为它是一个循环,它依赖于一个常数因子的数组大小:big-O表示法忽略任何常数因子.O(n)意味着对算法的唯一影响是基于数组的大小.它实际上需要一半的时间,对于大O来说并不重要.

换句话说:如果你的算法需要一定的时间n+X,Xn,Xn + Y都将归结为大O O(n).

如果循环的大小改变而不是常数因子,它会变得不同,但是作为对数或指数函数n,例如,如果大小是100和循环2,则大小是1000和循环3,大小是10000和循环4.在那种情况下,例如,它将是O(log(n)).

如果循环与大小无关,也会有所不同.即,如果你总是循环100次数,无论循环大小如何,你的算法都会O(1)(即,在一些恒定的时间内运行).

我也想知道我想出的那个等式是否在某个地方是正确的.

是.事实上,如果你的等式最终成为某种形式n * C + Y,那么它C就是一些常数和Y是一些其他值,结果是O(n),无论看见是大于1还是小于1.