2

我必须写下我必须为我的作业想出的算法的大 O 表示法。

我可以说下面的代码是O(n^2). 因为对于每一个 x，我都必须经历所有的 y，随着世界变得越来越大，它变得越来越慢。

int[][] world = new world[20][20];
for (int x = 0; x < 20; x++)
{
    for (int y = 0; y < 20; y++)
    {
        ..
    }
}

但是，对于另一个问题，我必须经过世界的下半部分，所以我的 y 循环减半。

int[][] world = new world[20][20];
for (int x = 0; x < 20; x++)
{
    for (int y = 10; y < 20; y++)
    {
        ..
    }
}

我不太确定什么大 O 表示法适用于上述循环，是否仍然O(n^2)是因为世界越大它仍然变得越慢？还是O(log n)因为 y 减半了？

4

3 回答 3

10

简单地说O(n*n/2)=O(n^2)，因为在大 O 中没有考虑常量。

于 2012-09-10T11:15:05.463 回答
4

因为O(n^2)y 仍然是 n 的函数，即O(n^2/2)仍然是O(n^2)。

于 2012-09-10T11:16:08.287 回答
4

您的两种算法实际上都是 O(n) （假设 n 是输入中的位数，这是常见的定义）。第一个触摸世界数组中的每个“像素”一次，所以很容易看出它是 O(n)。第二个触摸了一半的像素，但仍然是 O(n)，因为 O(n/2) = O(n)。在这两种情况下，将世界数组的大小加倍或多或少都会使执行时间加倍，这是 O(n) 算法的典型特征。

于 2012-09-10T11:28:49.457 回答