Алгоритм

From

Evgenij Masherov (2:5020/175.2)

To

Alexander Pashchenko

Date

2002-10-09T09:46:57Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Tue Oct 08 2002 23:01, Alexander Pashchenko wrote to desyatnik@dax.ru:

 AD>> Вопреки предлагаемому массив сортировать НЕ надо.
 AD>> Почему? При неотсортированном массиве алгоритм очевиден -
 AD>> перебор с ограничением (в худшем случае будем сравнивать
 AD>> каждый элемент с каждым). Сложность алгоритма О((m*n)^2).

 AP> Кстати, я так и не разобрался, что сие  ^^^^^^^^^^^^^^^^^^^^ значит.
 AP> Может кто-нить объяснить доступными для понимания (10-11 класс) словами.

При анализе скорости алгоритма в зависимости от объема исходных данных разные
его части требуют разного времени, и это время растет с разной скоростью.
Поэтому, для упрощения работы, рассматривают только наиболее существенно
возрастающую часть работы. При этом, поскольку время работы обратно
пропорционально производительности конкретной машины, при сравнении алгоритмов
пренебрегают постоянным множителем. Указанное обозначение понимается в смысле
- время работы алгоритма при больших Эм и Эн будет приблизительно
пропорционально величине под знаком О().

 AD>> Сортировка (и тем более хэши) имеют смысл при
 AD>> структурах и задачах баз данных, но никак не
 AD>> числовых матриц (тем более, как я подозреваю,
 AD>> повторный поиск производиться не будет :)

 AP> ЗЫ а вдобавок доступно объяснить, что такое хэш?

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

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)