Крупнейшие и наименьшие элементы списка

Ответ 1

Оптимальный алгоритм принимает 3/2 * n сравнения.

Он работает следующим образом:

5 2 6 7 3 1 10 35 4 6

• [5] [6]
  
• [5, 2], [6, 4]
  
• [5, 2, 6], [6, 4, 35]
  
• [5, 2, 6, 7], [6, 4, 35, 10]
  
• [5, 2, 6, 7, 1], [6, 4, 35, 10, 3]
  

На каждом шаге (n/2) вы сравниваете i-й и n-й-й элементы и переходите к таблице "больше" и "ниже"

После n/2 шагов вы знаете, что минимум находится в "нижней" таблице, а максимум - в "большой" таблице. Findin min и max в этих двух таблицах (n/2) * 2, поэтому у вас есть (3/2) * n

Ответ 2

Это N * (3/2).

Ответ 3

Нижняя граница (реконструирована из памяти, не уверен, что должен делать цитирование)

Вот противник, который заставляет (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 в графе сравнения.

Ответ 4

Это можно сделать с помощью

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];
}  

Ответ 5

Если вы сравниваете числовые значения, это действительно можно сделать без каких-либо сравнений! Трюк состоит в том, чтобы расширить бит знака разницы между двумя значениями и использовать его как двоичную маску.

Возможно, это скорее хитроумный трюк, чем ответ на "компьютерный уровень", который вы ищете, но, в зависимости от компилятора и процессора, следующее может быть быстрее, чем альтернативы, которые используют операторы 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-разрядных регистров).

Ответ 6

Это действительно где-то между 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. Для всех остальных это будет где-то посередине.

Ответ 7

Здесь является хорошим объяснением с рабочим кодом. Сложность - O ((3n/2) - 2).

Он также объясняет случай массива нечетного размера, в котором вы просто добавляете дополнение.

Ответ 8

Использовать алгоритм 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);
   }
}

Ответ 9

Я предполагаю, что это будет (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;
}