所以我有这个算法,我正在尝试确定算法分析问题的基本操作。
代码如下:
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 语句为真时发生的代码执行。有人可以在算法分析方面给我一个可靠的解释,这个算法的基本操作是什么:) 请非常感谢
最佳答案
基本操作可能是这样的:
- 数组索引
- 条件,即
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)
行。
希望这对您有所帮助。
关于c++ - 这个给定算法中的 "basic operation"究竟是什么,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42883772/