-1

我在下面的代码中为 if 语句找到大 O 时遇到了一些麻烦：

public static boolean areUnique (int[] ar)
{
    for (int i = 0; i < ar.length-1; i++) // O(n)
    {
        for (int j = i+1; j < ar.length-1; j++) // O(n)
        {
            if (ar[i] == ar[j]) // O(???)
                return false; // O(1)
        }
    }

    return true; //O(1)
}

我正在尝试针对最佳、最差和平均情况进行时间复杂度分析

谢谢大家这么快回答！我不确定我最好的最坏情况和平均情况是否正确......应该存在大小写差异，而不是因为 if 语句？但是当我进行分析时，我将它们全部结束为 O(n 2 )

  • 最佳：O(n) * O(n) * [O(1) + O(1)] = O(n 2 )
  • 最差：O(n) * O(n) * [O(1) + O(1) + O(1)] = n 2
  • 平均：O(n) * O(n) * [O(1) + O(1) + O(1)] = O(n 2 )

我这样做对吗？我的教科书不是很有帮助

4

3 回答 3

1

首先，这条线

if (ar[i] == ar[j])

总是需要时间 Θ(1) 来执行。它只做固定数量的工作（比较加上一个分支），所以这里完成的工作不会渐近地贡献于整个运行时。

鉴于此，我们可以通过考虑如果该陈述始终为假会发生什么来分析最坏情况下的行为。这意味着循环尽可能长地运行。正如您所注意到的，由于每个循环都运行 O(n) 次，因此在最坏的情况下，完成的总工作量为 Θ(n 2 )。

然而，在最好的情况下，运行时间要短得多。想象一下前两个元素相同的任何数组。在这种情况下，当第一次遇到条件时，函数几乎会立即终止。在这种情况下，运行时间为 Θ(1)，因为将执行恒定数量的语句。

然而，平均情况在这里并没有很好地定义。平均情况通常是相对于某些分布定义的——平均值是什么？- 不清楚这是什么。如果您假设数组由真正的随机int值组成，并且ints 可以取任何整数值（这不是一个合理的假设，但现在没问题），那么随机选择的数组具有重复项的概率为 0，我们重新回到最坏的情况（运行时 Θ(n 2 )）。但是，如果这些值受到更多约束，则运行时会发生变化。假设数组中有 n 个数字，整数范围从 0 到 k - 1，包括 0 到 k - 1。给定一个随机数组，运行时间取决于

  • 是否有任何重复，以及
  • 如果有重复，则第一个重复值出现在数组中。

我相当有信心，这个数学将很难计算出来，如果我今天晚些时候有时间，我会回来尝试得到一个准确的值（或者至少是渐近合适的值）。我严重怀疑这是预期的结果，因为这似乎是一个介绍性的大 O 任务，但这是一个有趣的问题，我想更多地研究它。

希望这可以帮助！

于 2013-10-15T17:40:43.727 回答
0

您可以将其视为 O(1)。

无论你认为什么是“一步”，

执行 a[i] == a[j] 的说明不依赖于

在这种情况下，值 n。

于 2013-10-15T15:56:01.223 回答
0

if 本身是 O(1)；

这是因为它没有考虑 ALU 或 CPU 中的进程，所以 if(ar[i] == ar[j]) 实际上是 O(6)，转换为 O(1)

于 2013-10-15T15:53:30.817 回答