6

如果数组中至少有两个值是，则该方法hasTwoTrueValues返回。为建议的所有三个实现提供 Big-O 运行时间。truebooleantrue

//版本 1

public boolean hasTwoTrueValues(boolean[] arr) {
    int count = 0;
    for(int i = 0; i < arr.length; i++)
        if(arr[i])
            count++;
        return count >= 2;
}

//版本 2

public boolean hasTwoTrueValues(boolean[] arr) {
    for(int i = 0; i < arr.length; i++)
        for(int j = i + 1; j < arr.length; j++ )
            if(arr[i] && arr[j])
                return true;
}

//版本 3

public boolean hasTwoTrueValues(boolean[] arr) {
    for(int i = 0; i < arr.length; i++)
        if(arr[i])
            for(int j = i + 1; j < arr.length; j++)
                if(arr[j])
                    return true;
                        return false;
}

这些是我的答案：

  • 版本 1是O(n)
  • 版本 2是O(n^2)
  • 版本 3是O(n^2)

我对这个 Big-O 表示法真的很陌生，所以如果我的答案是正确/不正确的，我需要指导。如果我错了，你能解释一下并帮助我学习吗？

4

2 回答 2

4

版本 1 非常简单并且线性运行，因此其运行时间平均为 O(n)。

版本 2 更有趣一些。它平均以 n(n-1) 运行，即 O(n 2 )。这个循环有一个早期return，所以它肯定有可能早在前两个元素就中断。

第 3 版更棘手。你必须小心这一点。第二个循环只会在arr[i]is时运行true。然后，它的运行时间必须分为不同的类别。

  • 如果数组的所有元素都是假的，那么你的运行时间将是 O(n)。
  • 如果数组的一半元素为真，那么您将在 (n(n-1))/2 的条件下运行第二个循环，即 O(n 2 )。
  • 如果数组的所有元素都为真，那么您将在 O(n 2 ) 中运行。您还将在前两个元素之后立即退出，但您仍然使用两个循环来执行操作。

可以肯定地说，版本 3 的平均和最差运行时间将是 O(n 2 )。最好是 O(n)，这绝对是可能的。

于 2012-10-01T03:52:49.180 回答
0

简而言之，最坏情况的运行时间是： 版本 1：O(n)
版本 2：O(n^2)
版本 3：O(n)

更详细的分析...

对于此算法，您必须考虑最佳情况、最坏情况和平均情况运行时才能进行有意义的比较。

对于它们中的每一个，以下应举例说明：

bestCase = [ true, true, ...] // the first two are true
worstCase = [ false, false, ..., false] // all are false
averageCase = [ true, ..., true, ..., false // second true value is found about half-way

对于您的所有算法，最佳情况下的运行时间是O(2)，表示恒定时间。

在最坏的情况下，您的第一个算法是O(n)，表示线性运行时。但是，在最坏的情况下，您的第二种算法会非常具体地退化，因为在每一步中，您要检查的元素都会减少一个。您最终得到 summation n + (n-1) + (n-2) + ...，它将评估为n(n-1)/2哪个，正如您正确所说的那样，在 中O(n^2)，并以二次方增长。

在所有都为假的“最坏情况”中（正如我们将看到的，这实际上不是版本 3的最坏情况），您的第三个算法实际上在线性时间内运行，因为该if语句阻止了第二个循环运行.

事实证明，版本 3永远不会在二次时间中运行：它在平均和最坏的情况下是线性的，因为它线性扫描第一个，然后只在发现之后才true线性扫描其余的第二个，尽管它没有true甚至不工作！因为您的内部 for 循环中有两个返回，所以一旦遇到第一个值，如果下一个直接邻居是true，它将返回。但是，如果下一个直接邻居是，它会立即返回并且不检查任何其他值。这意味着在输入上：truetruefalsefalse

[ true, false, true ]

版本 3一看到第二个 false 值就会返回 false。（从技术上讲，我在这里假设您希望return false在 for 循环内执行此操作，在这种情况下，您还需要添加{ }，同样使用您的第一个版本。虽然并非总是必要的，但它有助于澄清到底发生了什么，特别是因为这与您当前的缩进不匹配。当不存在时，循环/if 主体中仅包含紧随其后的语句。）我怀疑，即使正确实施，*版本 3仍将具有线性的最坏情况运行时间, 在输入上：

[true, false, false, ..., false]

第一个 true 将导致它n在内循环中扫描时间，但随后外循环将继续运行到 n 而不再次运行内循环，总共为您提供 2n-1 次操作，这当然是在O(n).

如果您{ }是正确的并且只是您的缩进是错误的，那么这些分析可能需要稍微修改，但这是您需要应用于大 O 问题（以及一般的渐近分析）的那种思维方式。

于 2012-10-01T04:23:27.890 回答