Алгоритм недели: минимум и максимум

Вступление

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

 

Первое, что нужно отметить, это то, что мы проходим через массив с n шагами и нам нужно ровно n-1 сравнений Понятно, что это оптимальное решение, потому что мы должны проверить все элементы. Конечно, мы не можем быть уверены, что нашли минимальное (максимальное) значение без проверки каждого отдельного значения.

обзор

Приведенный выше алгоритм очень прост, и мы уверены, что он оптимален. Очевидно, что нахождение как минимального, так и максимального значения составляет O (n) с n-1 сравнениями, но как насчет объединения этих задач в один проход?

Нахождение максимума идентично нахождению минимума и требует n-1 сравнений!

Поскольку они оба являются O (n) и нуждаются в n-1 сравнениях, естественно думать, что объединение двух задач будет O (n) и 2n — 2 сравнениями. Однако мы можем уменьшить количество сравнений!

Вместо того, чтобы брать только один элемент из массива и сравнивать его с минимумом и максимумом, мы можем взять пару элементов на каждом шаге. Таким образом, мы можем сначала сравнить их, а затем сравнить меньшее значение с наименьшим на данный момент значением, а больший элемент — с наибольшим на данный момент значением. Это сделает только 3 сравнения вместо 4.

Реализация

Легко реализовать минимальные (максимальные) алгоритмы за один цикл.

$list = array(3,4,2,5,6,7,8,2,5,1,4,4,6);
 
function minimum($list)
{
	$len = count($list);
	$minimum = $list[0];
 
	for ($i = 1; $i < $len; $i++) {
		if ($minimum > $list[$i]) {
			$minimum = $list[$i];
		}
	}
 
	return $minimum;
}
 
// 1
echo minimum($list);

Реализация нахождения максимума практически одинакова.

$list = array(3,4,2,5,6,7,8,2,5,1,4,4,6);
 
function maximum($list) 
{
	$len = count($list);
	$maximum = $list[0];
 
	for ($i = 1; $i < $len; $i++) {
		if ($maximum < $list[$i]) {
			$maximum = $list[$i];
		}
	}
 
	return $maximum;
}
 
// 8
echo maximum($list);

Простое объединение этих двух функций приведет нас к O (n) с 2n — 2 сравнительным решением.

$list = array(3,4,2,5,6,7,8,2,5,1,4,4,6);
 
function min_and_max($list) 
{
	$len = count($list);
	$minimum = $maximum = $list[0];
 
	for ($i = 1; $i < $len; $i++) {
		if ($minimum > $list[$i]) {
			$minimum = $list[$i];
		}
		if ($maximum < $list[$i]) {
			$maximum = $list[$i];
		}
	}
 
	return array('minimum' => $minimum, 'maximum' => $maximum);
}
 
min_and_max($list);

Однако мы можем взять пару пунктов на каждом шаге. Сначала мы сравним элементы из этой пары, а затем сравним их соответственно с минимальным и максимальным значением. Поскольку на каждой итерации мы прыгаем на два элемента, в случае, если количество элементов массива четное, мы должны проверять границы массива. Это можно преодолеть, добавив центинель. Таким образом, элементы массива всегда нечетные, но это приведет нас к «дополнительному» решению для памяти.

часовой

function min_and_max($list) 
{
	$len = count($list);
	$minimum = $maximum = $list[0];
 
	// adding a centinel
	if ($len % 2 == 0) {
		$list[] = $list[0];
	}
 
	for ($i = 1; $i < $len; $i+=2) {
 
		if ($list[$i] < $list[$i+1]) {
			if ($minimum > $list[$i]) {
				$minimum = $list[$i];
			}
			if ($maximum < $list[$i+1]) {
				$maximum = $list[$i+1];
			}
		} else {
			if ($minimum > $list[$i+1]) {
				$minimum = $list[$i+1];
			}
			if ($maximum < $list[$i]) {
				$maximum = $list[$i];
			}
		}
	}
 
	return array('minimum' => $minimum, 'maximum' => $maximum);
}
 
min_and_max($list);

Без стража

function min_and_max($list) 
{
	$len = count($list);
	$minimum = $maximum = $list[0];
 
	$start = 1;
	if (!($len & 1)) {
		$start = 0;
	}
 
	for ($i = $start; $i < $len; $i+=2) {
 
		if ($list[$i] < $list[$i+1]) {
			if ($minimum > $list[$i]) {
				$minimum = $list[$i];
			}
			if ($maximum < $list[$i+1]) {
				$maximum = $list[$i+1];
			}
		} else {
			if ($minimum > $list[$i+1]) {
				$minimum = $list[$i+1];
			}
			if ($maximum < $list[$i]) {
				$maximum = $list[$i];
			}
		}
	}
 
	return array('minimum' => $minimum, 'maximum' => $maximum);
}
 
min_and_max($list);

сложность

Сложность нахождения как минимума, так и максимума составляет O (n). Даже после объединения обоих алгоритмов за один проход сложность остается O (n). Однако во втором случае мы можем уменьшить количество сравнений до 3 * ceil (n / 2) вместо 2n — 2!

заявка

Этот алгоритм может быть применен в различных областях информатики, так как его природа настолько проста. Однако есть две причины, почему этот подход так важен.

Во-первых, мы видим, как объединение двух «алгоритмов» не означает, что мы объединяем их сложности или количество операций. С хитрым трюком и с наблюдением, что две операции связаны (минимальная и максимальная), мы можем уменьшить количество сравнений.

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

Вы отличный разработчик? Нажмите здесь, чтобы ответить на еженедельную викторину!