algorithm - 计算基本操作

Question

我需要计算以下代码的基本操作:

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 条件和嵌套在该 block 中的语句)。但我不确定这是什么原始操作。

Answer 1

在循环迭代之前

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个指针加法

因此，您看到由您决定什么是“基本操作”，所有答案都同样正确。