1

我需要计算下面代码的基本操作：

public static int findmax(int[] a, int x) {
    int currentMax = a[0];

    for (int i = 1; i < a.length; i++) {
        if (a[i] > currentMax) {
        currentMax = a[i];
        }
    }

    return currentMax;
}

我知道原始操作（例如为变量赋值）的值是1. 所以这里a[0]为执行的原始操作分配currentMax帐户。1

在 for 循环中：分配1给i，也说明1。和i < a.length，并且i++是n - 1每个（即2(n-1)）。但是，我对如何处理该if声明感到困惑。我知道我们正在寻找最坏的情况（因此我们需要执行if条件和嵌套在该块中的语句）。但我不确定这在原始操作方面是什么。

4

1 回答 1

3

在循环迭代之前

int currentMax = a[0];

作业：计为1。

int i = 1

作业：计1

对于循环的 n 次迭代中的每一次（注意这里，n=a.length-1）

i < a.length

比较（返回真）：计为1

i++

增量：计为1

a[i] > currentMax

比较：计为1

currentMax = a[i];

分配：计为1

当存在循环时

i < a.length

比较（返回 false）：计为1

结论

在最坏的情况下，你有 1 + 1 + n*(1+1+1+1) + 1 = 4*n + 3 个基本操作，因此你的算法的复杂性是 Θ(n)。

更具体地说，要处理 if 语句，您当然必须考虑其参数的计算，但“if”这个词本身并不重要。处理器只是根据结果立即跳转到下一条指令。有些人可能会争辩说，这种条件跳转可能算作 1，但无论如何这并不重要，因为 4*n + 3 与 5*n + 3 的复杂度相同，即 Θ(n)。

如果您想精确并保持常量，那么您必须指定它的确切含义，例如：

  • n+2 个作业
  • n 个增量
  • 2*n+1 次比较

在这种情况下，很清楚您决定将什么算作基本操作。但例如，您也可以决定像访问数组一样a[i]值得计数（它实际上是一个指针加法加上一个内存访问），因此您将添加：

  • 2*n+1 数组访问

或者，如果您想更精确，并区分访问之一是a[0]和不执行指针算术这一事实，您会说：

  • 2*n+1 内存访问
  • 2*n 指针加法

因此，您会看到由您决定将什么视为“基本操作”，并且所有答案都同样正确。

于 2013-09-06T05:01:49.590 回答