6

1) 

  x = 25;
    for (int i = 0; i < myArray.length; i++)
    {
        if (myArray[i] == x)
            System.out.println("found!");
    }

我认为这是O（n）。

2)

for (int r = 0; r < 10000; r++)
    for (int c = 0; c < 10000; c++)
        if (c % r == 0)
            System.out.println("blah!");

我认为这个是 O(1)，因为对于任何输入 n，它将运行 10000 * 10000 次。不确定这是否正确。

3)

a = 0
for (int i = 0; i < k; i++)
{
    for (int j = 0; j < i; j++)
        a++;
}

我认为这个是 O(i * k)。我真的不知道如何解决这样的问题，其中内部循环受到外部循环中递增的变量的影响。这里的一些关键见解将不胜感激。外循环运行 k 次，内循环运行 1 + 2 + 3 + ... + k 次。所以这个总和应该是 (k/2) * (k+1)，这将是 k^2 的顺序。那么它实际上是O（k ^ 3）吗？这似乎太大了。再次，不知道如何处理这个问题。

4)

int key = 0;    //key may be any value
int first = 0;
int last = intArray.length-1;;
int mid = 0;
boolean found = false;

while( (!found) && (first <= last) )
{
    mid = (first + last) / 2;

    if(key == intArray[mid]) 
        found = true;
    if(key < intArray[mid])
        last = mid - 1;
    if(key > intArray[mid]) 
        first = mid + 1;
}

这个，我认为是 O(log n)。但是，我得出这个结论是因为我相信这是一个二分搜索，而且我从阅读中知道运行时间是 O(log n)。我认为这是因为对于循环的每次迭代，您将输入大小除以 2。但是，我不知道这是否是正确的推理，或者如何处理我没有见过的类似算法，并且能够推断出它们以更可验证或更正式的方式在对数时间内运行。

5)

int currentMinIndex = 0;

for (int front = 0; front < intArray.length; front++)
{
    currentMinIndex = front;

    for (int i = front; i < intArray.length; i++)
    {
        if (intArray[i] < intArray[currentMinIndex])
        {
            currentMinIndex = i;
        }
    }

    int tmp = intArray[front];
    intArray[front] = intArray[currentMinIndex];
    intArray[currentMinIndex] = tmp;
}

我对这个感到困惑。外循环运行 n 次。内部 for 循环运行 n + (n-1) + (n-2) + ... (n - k) + 1 次？那是 O(n^3) 吗？

4

3 回答 3

2

或多或少，是的。

1 是正确的 - 似乎您正在搜索我认为是未排序集合中的特定元素。如果是这样，最坏的情况是元素位于列表的最后，因此 O(n)。

2是正确的，虽然有点奇怪。它是 O(1) 假设r并且c是常数并且边界不是变量。如果它们是恒定的，那么是 O(1)，因为没有什么可输入的。

3 我相信这仍然被认为是 O(n^2)。会有一些常数因子，如 k * n^2，去掉常数，你得到 O(n^2)。

4 看起来很像排序集合的二进制搜索算法。O(logn) 是正确的。它是日志，因为在每次迭代中，您基本上将您要查找的元素所在的可能选择数量减半。

由于与 3 类似的原因，5 看起来像冒泡排序 O(n^2)。

于 2012-07-13T19:39:16.777 回答
1

O() 本身没有任何意义：您需要指定是在计算“最坏情况”O 还是平均情况 O。对于某些排序算法，它们平均有 O(n log n)但在最坏的情况下是 O(n^2)。

基本上你需要计算最内层循环的总迭代次数，并在没有任何常数的情况下取结果的最大分量（例如，如果你有 k*(k+1)/2 = 1/2 k^2 + 1/2 k，最大的分量是 1/2 k^2，因此你是 O(k^2))。

例如，您的项目 4) 在 O(log(n)) 中，因为如果您处理大小为 n 的数组，那么您将在该数组上运行一次迭代，下一次将在大小为 n 的数组上运行/2，然后是 n/4，...，直到这个大小达到 1。所以它是 log(n) 次迭代。

于 2012-07-13T19:43:17.800 回答
1

您的问题主要是关于 O() 的定义。

当有人说这个算法是 O(log(n)) 时，你必须阅读：

当输入参数n变得很大时，算法执行的操作数最多增长log(n)

现在，这意味着两件事：

  1. 您必须至少有一个输入参数 n。没有一个就谈论 O() 是没有意义的（就像你的情况2一样）。
  2. 您需要定义要计数的操作。这些可以是添加，两个元素之间的比较，分配的字节数，函数调用的数量，但你必须决定。通常你会采取对你来说成本最高的手术，或者如果做太多次就会变得昂贵的手术。

所以记住这一点，回到你的问题：

  1. n 是 myArray.Length，您计算的操作数是 '=='。在这种情况下，答案正好是 n，即 O(n)

  2. 你不能指定一个 n

  3. n只能是k，你算的操作数是++。正如您所说，您恰好有 k*(k+1)/2 即 O(n2)

  4. 这次n又是你数组的长度，你算的操作是==。在这种情况下，操作的数量取决于数据，通常我们谈论“最坏情况”，意思是在所有可能的结果中，我们看最耗时的那个。该算法充其量只进行一次比较。对于最坏的情况，让我们举个例子。如果数组是 [[1,2,3,4,5,6,7,8,9]] 并且您正在寻找 4，则您的 intArray[mid] 将依次变为 5、3 和 4，依此类推您将进行 3 次比较。事实上，对于一个大小为 2^k + 1 的数组，最大比较次数为 k（你可以查看）。所以 n = 2^k + 1 => k = ln(n-1)/ln(2)。您可以将此结果扩展到 n 不 = 2^k + 1 的情况，您将得到复杂度 = O(ln(n))

无论如何，我认为您很困惑，因为您不完全知道 O(n) 的含义。我希望这是一个开始。

于 2012-07-13T21:54:15.393 回答