单个 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 的例子，但是 none 非常像这样，其中迭代器基本上同时递增和修改数组。

它有一个循环这一事实让我觉得它无论如何都是 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。

Answer 2

关于循环，你是对的。循环将确定大 O。但是循环运行只针对数组的一半。

原来如此。 2 + 6 *(n/2)

如果我们让n很大，其他的数就真的很小了。所以他们不会重要。所以它的 O(n).

假设您正在运行宁 2 个独立的循环。 2 + 6* (n/2) + 6*(n/2) 。在那种情况下，它将再次成为 O(n)。

但是如果我们运行嵌套循环。 2+ 6*(n*n)。那么它将是 O(n^2)

始终删除常量并进行数学计算。你明白了。

Answer 3

随着j-i每次迭代减少2个单位，其中N/2个被取走（假设N=length(a)）。

因此运行时间确实是 O(N/2)。 O(N/2) 严格等同于 O(N).

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

Big-Oh notation for a single while loop covering two halves of an array with two iterator vars

java

algorithm

big-o