计数基本运算

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分配给currentMax帐户。

在for循环中:将1分配给i，也是1的帐户。i < a.length和i++分别是n - 1 (即2(n-1))。但是，对于如何处理if语句，我感到困惑。我知道我们正在寻找最坏的情况(因此我们需要执行if条件和嵌套在该块中的语句)。但我不知道这是什么在一个原始的操作。

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

因此，你可以看到，由你来决定什么是“基本运算”，所有的答案都是同样正确的。