Re: Алгоритм

From

Sergey Andrianov (2:5020/1507.400)

To

Alexander Pashchenko

Date

2002-10-09T19:27:40Z

Area

RU.ALGORITHMS

Здравствуй, Alexander!

Однажды 09-Oct-02  в 00:01   Alexander Pashchenko (2:5062/17.212)
написал       desyatnik@dax.ru    по поводу
-=-   Алгоритм  -=-

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

	Если количество операций или время (что то же самое) при выполнении алгоритма
при больших n ведет себя как C*F(n), где С - константа , то говорят, что
сложность алгоритма O(F(n)). При этом принято, что F(n) не должна содержать
слагаемых. Например A*x^2 + B*x + C имеет сложность O(x^2), т.к. при больших n
линейный член и константа становятся исчезающе малы по сравнению с квадратичным
членом.

AD>> Теперь рассмотрим сортировку - неважно какой алгоритм.
AP> [skip]
AD>> 4 9 10 11
AP> Скорость абсолютно не важна. Главное, чтобы было понятно и изящно.

	Обыно считается, что "изящно" должно включать в себя "быстро".
 
AP> В голову лезут только вложенные циклы с исключением пройденных элементов, 
AP> но что-то мне подсказывает, что там бага, к тому же это далеко не изящно.
AD>> Дальше, думаю, рассматривать не стоит... :)
AP> Да и вопрос-то был теоритический.
AD>> Сортировка (и тем более хэши) имеют смысл при
AD>> структурах и задачах баз данных, но никак не
AD>> числовых матриц (тем более, как я подозреваю,
AD>> повторный поиск производиться не будет :)
AP> ЗЫ а вдобавок доступно объяснить, что такое хэш?

	Один из способов увеличить скорость за счет расхода дополнительной памяти. 
	Ну, тебе это не интересно... :)


                  До свидания,  в  20:20 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)