c++ - 这个给定算法中的 "basic operation"究竟是什么

Question

所以我有这个算法，我正在尝试确定算法分析问题的基本操作。

代码如下:

median(int array[]){
int k = array.length();
int n = k/2;
    for(int i = 0; i < k; i++){
    int numsmaller = 0;
    int numequal = 0;
        for(int j = 0; j < k; k++){
        if(array[j] < array[i]){
        numsmaller++;
        }else
        if(array[j] == array[i]){
        numequal++;
        }
if(numsmaller < n && n <= (numsmaller + numequal){
return array[i]
}
                                   }//inner loop
                                 }//outter loop
}//end of function

我目前的印象是，该算法的基本操作是函数内部循环中的两个 if 语句。令我困惑的是，我不确定基本操作是否是 bool 表达式本身，它会在每次迭代时执行，检查 array[j] < array[i] 以及 array[j] 是否等于 array[i]。 Or weather 基本操作是当任一 if 语句为真时发生的代码执行。有人可以在算法分析方面给我一个可靠的解释，这个算法的基本操作是什么:) 请非常感谢

Answer 1

基本操作可能是这样的:

• 数组索引
• 条件，即 if (x == y)
• 赋值，即 x = 10
• 甚至是基本的数学运算，即 y + 2

请注意，这无论如何都不是详尽的列表。另请注意，某些代码的最坏情况需要执行最大数量的基本操作；所以在下面的代码中，您将看到最坏情况下的三个基本操作。

if (variable == true) {
  int x = y + 2;
}

...这是因为我们实际上只是组合了上面的几个列表项。我们必须执行第一个条件，无论一个(一个基本操作)，但之后“最坏情况”是 variable = true，因为我们然后继续执行赋值。当然，为了计算 x 将通过赋值假定的非显而易见的值，我们必须执行另一个基本操作(y 和 2 之间的算术)，这给了我们一共三个基本操作。

因此，在您的情况下，在内部循环中执行的基本操作是条件，在满足其中一个条件的情况下变量的递增(基本上是赋值)，以及两个条件加上在

if(numsmaller < n && n <= (numsmaller + numequal)

行。

希望这对您有所帮助。