Оба эти алгоритма верны (если, конечно, массив не пуст). Я думаю, что версия А работает в более общем смысле, поскольку для некоторых типов (в частности, для строк) не может быть четко определенного максимального значения.
Причина, по которой эти алгоритмы эквивалентны, связана с классным математическим объектом, называемым полурешёткой . Чтобы мотивировать полурешетки, есть несколько интересных свойств max, которые оказываются справедливыми:
- max = idempotent , поэтому применение его к одному и тому же значению дважды возвращает исходное значение: max (x, x) = x
- max равно коммутативно , поэтому не имеет значения, в каком порядке вы применяете его к аргументам: max (x, y) = max (y, x)
- max равно ассоциативно , поэтому, принимая максимум три или более значений, не имеет значения, как вы группируете элементы: max (max (x, y), z) = max (x, max (y, z))
Эти законы также применимы как к минимуму, так и ко многим другим структурам. Например, если у вас есть древовидная структура, оператор «наименьшей верхней границы» также удовлетворяет этим ограничениям. Точно так же, если у вас есть набор множеств и объединение или пересечение множеств, вы обнаружите, что эти ограничения также выполняются.
Если у вас есть набор элементов (например, целые числа, строки и т. Д.) И некоторый двоичный оператор, определенный над ними с указанными выше тремя свойствами (идемпотентность, коммутативность и ассоциативность), то вы нашли структуру, называемую полурешетка . Затем бинарный оператор называется оператором встречи (или иногда оператор соединения в зависимости от контекста).
Причина, по которой полурешетки полезны, состоит в том, что если у вас есть (конечная) коллекция элементов, взятых из полурешетки, и вы хотите вычислить их соответствие, вы можете сделать это с помощью цикла, подобного следующему:
Element e = data[0];
for (i in data[1 .. n])
e = meet(e, data[i])
Причина, по которой это работает, заключается в том, что, поскольку оператор встречи является коммутативным и ассоциативным, мы можем применить встречу к элементам в любом порядке, который нам нужен. Применяя его по одному элементу за раз, когда мы проходим по элементам массива по порядку, мы получаем такое же значение, как если бы мы сначала перетасовывали элементы массива или повторяли в обратном порядке и т. Д. В вашем случае оператор встречи был " max "или" min ", и так как они удовлетворяют законам для операторов удовлетворения, описанным выше, приведенный выше код будет правильно вычислять max или min.
Чтобы ответить на ваш первоначальный вопрос, нам нужно немного больше терминологии. Вам было любопытно, было ли лучше или безопаснее инициализировать исходное предположение о минимальном значении, которое будет максимально возможным целым числом. Причина, по которой это работает, в том, что у нас есть классное свойство, которое
min(int.MAX_VALUE, x) = min(x, int.MAX_VALUE) = x
Другими словами, если вы вычислите встречу int.MAX_VALUE и любое другое значение, вы получите второе значение обратно. В математических терминах это происходит потому, что int.MAX_VALUE является верхним элементом полурешетки встречи. Более формально, верхний элемент для полурешетки Meet - это элемент (обозначаемый как & top;), удовлетворяющий
встреча (& top;, x) = встреча (x, & top;) = x
Если вы используете max вместо min, тогда верхний элемент будет int.MIN_VALUE, так как
max(int.MIN_VALUE, x) = max(x, int.MIN_VALUE) = x
Потому что применение оператора Meet к & top; и любой другой элемент создает этот другой элемент. Если у вас есть полурешетка встречи с четко определенным верхним элементом, вы можете переписать приведенный выше код, чтобы вычислить соответствие всех элементов как
Element e = Element.TOP;
for (i in data[0 .. n])
e = meet(e, data[i])
Это работает, потому что после первой итерации e устанавливается на meet(e, data[0]) = meet(Element.TOP, data[0]) = data[0] и итерация продолжается как обычно. Следовательно, в вашем первоначальном вопросе не имеет значения, какой из двух циклов вы используете; до тех пор, пока определен хотя бы один элемент, они дают одинаковое значение.
Тем не менее, не все полурешетки имеют верхний элемент. Рассмотрим, например, набор всех строк, где оператор встречи определен как
meet(x, y) = x if x lexicographically precedes y
= y otherwise
Например, meet("a", "ab") = "a", meet("dog, "cat") = "cat" и т. Д. В этом случае нет строки s, удовлетворяющей свойству meet (s, x) = meet (x, s) = x, и поэтому полурешетка имеетнет верхнего элемента.В этом случае вы не сможете использовать вторую версию кода, потому что нет верхнего элемента, для которого вы можете инициализировать начальное значение.
Однако есть очень симпатичная техника, которую вы можете использовать для фальсификации этого, что на самом деле в конечном итоге привыкнуть немного на практике.Для заданной полурешетки без верхнего элемента вы можете создать новую полурешетку, у которой действительно есть верхний элемент, введя новый элемент ⊤ и произвольно определив, что встретить (⊤, x) = meet (x, ⊤) = x.Другими словами, этот элемент специально создан как верхний элемент и не имеет никакого значения в противном случае.
В коде вы можете вводить такой элемент неявным образом, написав
bool found = false;
Element e;
for (i in data[0 .. n]) {
if (!found) {
found = true;
e = i;
} else {
e = meet(e, i);
}
}
Этот кодработает с внешним логическим значением found, отслеживающим, видели ли мы первый элемент или нет.Если нет, то мы притворяемся, что элемент e - это новый верхний элемент.При вычислении соответствия этого верхнего элемента и элемента массива получается элемент массива, и поэтому мы можем просто установить элемент e равным этому элементу массива.
Надеюсь, это поможет!Извините, если это слишком теоретически ... Мне просто нравится математика.: -)