Какое минимальное количество сравнений требуется для поиска самых больших и наименьших элементов несортированного списка из n отдельных элементов?
Какая может быть лучшая временная сложность для вышеуказанного алгоритма?
Из минимального количества сравнений я хотел указать наиболее эффективный алгоритм для наихудшего случая.
Оптимальный алгоритм принимает 3/2 * n сравнения.
Он работает следующим образом:
5 2 6 7 3 1 10 35 4 6
На каждом шаге (n/2) вы сравниваете i-й и n-й-й элементы и переходите к таблице "больше" и "ниже"
После n/2 шагов вы знаете, что минимум находится в "нижней" таблице, а максимум - в "большой" таблице. Findin min и max в этих двух таблицах (n/2) * 2, поэтому у вас есть (3/2) * n
Это N * (3/2).
Нижняя граница (реконструирована из памяти, не уверен, что должен делать цитирование)
Вот противник, который заставляет (3/2) n - 2 сравнения, когда n четно, и (3/2) n - 3/2 сравнения, когда n нечетно. Алгоритм, описанный Марсином при тщательном анализе, достигает этих границ.
Каждый элемент находится в одном из четырех состояний: {min, max} (никогда не сравнивалось, поэтому может быть минимальным или максимальным), {min} (никогда не превышал другого элемента, поэтому может быть минимальным, но не максимальным), {max} (никогда не меньше, чем другой элемент, поэтому может быть максимальным, но не максимальным), {} (больше другого элемента, меньшего, чем другой элемент, не может быть ни минимумом, ни максимумом), где "может быть..." означает, что существует общий порядок, совместимый с сравнениями, выполняемыми алгоритмом, до сих пор в котором... выполняется.
Пусть T - сумма по элементам e мощности e-состояния. Вначале T = 2 n. В конце T = 2, так как иначе либо минимум, либо максимум не определяется однозначно. Следующий противник гарантирует, что T уменьшается не более чем на 2 при каждом сравнении и не более 1, если оба элемента не будут сравниваться в первый раз. Указанные границы следуют.
Противник должен предотвратить слишком быстрое снижение T, сохраняя хотя бы один согласованный общий порядок. Как противник определяет результат сравнения? Если ни один элемент не находится в состоянии {min, max}, тогда нам будет легко. Либо состояния различны, и в этом случае мы решаем согласно {min} {} < {max}, а T остается неизменным; или они одинаковы, мы даем произвольный согласованный ответ, а T уменьшается на 1. Докажем, что согласованность сохраняется. Предположим, что последнее сопоставление создает цикл. Все элементы цикла теперь должны находиться в состоянии {}, что возможно только в том случае, если оба ранее были в состоянии {}. Это противоречит нашей стратегии ответа последовательно для элементов в одном и том же состоянии.
В противном случае, по крайней мере, один из сравниваемых элементов находится в состоянии {min, max}. Если другое находится в состоянии {min}, тогда {min} < {min, max}. Если другое находится в состоянии {max}, то {min, max} < {max}. В противном случае, разрешите произвольно. Ясно, что T уменьшается на 2 тогда и только тогда, когда сравнение проводится между двумя элементами {min, max}. Это сравнение не создает цикл, потому что элемент в состоянии {min, max} имеет степень 1 в графе сравнения.
Это можно сделать с помощью
3*n/2-2 list element comparisons if n is even
3*(n-1)/2 list element comparisons if n is odd.
Вот код
minVal = maxVal = a[0];
int i;
for(i = 1; i < n-1; i += 2) {
if(a[i] < a[i+1]) {
if(a[i] < minVal)
minVal = a[i];
if(a[i+1] > maxVal)
maxVal = a[i+1];
}
else {
if(a[i+1] < minVal)
minVal = a[i+1];
if(a[i] > maxVal)
maxVal = a[i];
}
}
// here i == n-1 or i == n
if(i < n) {
if(a[i] < minVal)
minVal = a[i];
else if(a[i] > maxVal)
maxVal = a[i];
}
Если вы сравниваете числовые значения, это действительно можно сделать без каких-либо сравнений! Трюк состоит в том, чтобы расширить бит знака разницы между двумя значениями и использовать его как двоичную маску.
Возможно, это скорее хитроумный трюк, чем ответ на "компьютерный уровень", который вы ищете, но, в зависимости от компилятора и процессора, следующее может быть быстрее, чем альтернативы, которые используют операторы if:
void minmax(int values[], size_t count) {
int min = values[0];
int max = min;
for(int i = 1; i < count; ++i) {
int v = values[i];
int maxMask = (v - max) >> 31; // assuming 32-bit int
max = (max & maxMask) | (v & ~maxMask);
int minMask = (min - v) >> 31;
min = (min & minMask) | (v & ~minMask);
}
printf("max=%d min=%d\n", max, min);
}
Пример вызова:
int main() {
int values[] = {
20, -5, 13, -100, 55
};
minmax(values, 5); // prints max=55 min=-10
}
Сумма: 0 сравнений, за исключением тех, которые используются циклом, которые можно удалить, если вы разворачиваете цикл: -)
Хорошая вещь заключается в том, что она не использует условные переходы на уровне машинного кода, поэтому нет риска задержек трубопроводов. Этот алгоритм также можно легко расширить, чтобы сравнить сразу несколько значений (например, восемь байтов одновременно с использованием 64-разрядных регистров).
Это действительно где-то между n-1 и 2 (n-1), потому что вам нужно сравнивать каждый элемент с текущим max и min, но если первое сравнение возвращает true, вам не нужно делать второй
Удаление кода из другого ответа, мое решение выглядит следующим образом:
var largest = list[0];
var smallest = list[0];
for(var i=1;i<list.length;i++)
{
if(list[i] > largest) {
largest = list[i];
} else if(list[i] < smallest) {
smallest = list[i];
}
}
Если ваш исходный список сортируется в порядке возрастания, этот код сделает n-1 сравнения. Если он отсортирован в порядке убывания, он сделает 2n-2. Для всех остальных это будет где-то посередине.
Здесь является хорошим объяснением с рабочим кодом. Сложность - O ((3n/2) - 2).
Он также объясняет случай массива нечетного размера, в котором вы просто добавляете дополнение.
Использовать алгоритм maxmin [https://en.wikipedia.org/wiki/Minimax][minmax]
Число сравнений, необходимых для нахождения самых больших и наименьших элементов из n различных элементов, равно (3/2) n - 2..
nums - это набор чисел, а n (nums) - количество элементов в nums:
minMax (nums) {
if (n(nums) == 2) {
nums = {x, y};
return (max (x, y), min (x, y));
}
else {
divide nums equally into two sets, set1, set2;
minMax (set1);
minMax (set2);
}
}
Я предполагаю, что это будет (n-1) * 2 как
var largest = list[0];
var smallest = list[0];
foreach(var i in list.Skip(1))
{
if(i > largest)
largest = i;
else if(i < smallest)
smallest = i;
}