java - 单个 while 循环的 Big-Oh 表示法，该循环覆盖具有两个迭代器变量的数组的两半

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 的例子，但没有一个像这样迭代器基本上同时递增和修改数组。

它有一个循环这一事实让我认为它无论如何都是 O(n)。

有人介意帮我解决这个问题吗？

谢谢

Answer 1

The fact that it has one loop is making me think it's O(n) anyway.

这是正确的。不是因为它在做一个循环，而是因为它是一个循环，它取决于数组大小的一个常数因子:大 O 表示法忽略任何常数因子。 O(n) 表示对算法的唯一影响是基于数组的大小。它实际上只需要一半的时间，对于 big-O 来说无关紧要。

换句话说:如果您的算法需要时间 n+X、Xn、Xn + Y 都将归结为大 O O(n)。

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

如果循环与大小无关，也会有所不同。即，如果您始终循环 100 次，无论循环大小如何，您的算法都将是 O(1)(即，在某个恒定时间内运行)。

I was also wondering if the equation I came up with to get there was somewhere in the ballpark of being correct.

是的。事实上，如果你的等式最终是某种形式的 n * C + Y，其中 C 是某个常数，而 Y 是其他值，结果是O(n)，不管see是大于1，还是小于1。