Что именно является «базовой операцией»? в этом заданном алгоритме
Итак, у меня есть этот алгоритм, и я пытаюсь определить основную операцию для задачи анализа алгоритма.
вот код:
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 во внутреннем цикле функции.
Меня смущает то, что я не уверен, является ли основная операция самим логическим выражением, которое будет выполняться при каждой итерации, проверяя массив [j] < массив [i] и если массив [j] равен массиву [i]. Или, если основной операцией является выполнение кода, которое выполняется, когда любое из утверждений 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)
линия.
Надеюсь, это поможет.
Другие решения
Других решений пока нет …
detector