Я свами и не спорю.

Обычно алгоритмы оценивают, с точки зрения худшего случая. В худшем случае ваш алгоритм не линейный.

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


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

Значит, быстрая сортировка имеет асимптотику n^2?

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

P.S. Кажется, пора закругляться.
 

Ассимптотика и худший случай разные вещи.

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

В вашем же случае худший случай есть и для определенного вида данных. Ваш алгоритм не линейный.


резюмы: вы решили не задачу автора, а модифицировали задачу, дополнив ее некоторым ограничением. Кроме, того вы так и не привели докозательство правильности работы.


Вот решение аналогичное вашему. Предположим что для исходного массива выполнены условия применения ведерной-сортировки (backet sorting) отсортируем массив за линейное время и найдем в нем моду.


Это решение не хуже и не лучше вашего. Правда оно лучше тем, что док-во его правильности более прозрачно.

с ув. 

Этого не понял, какой-такой плохой вид данных?
Укажите пожалуйста, какой пункт алгоритма, кроме перебора значений входного массива требует времени, зависящего от N. По поводу пункта 1.2 я уже ответил.

В чем я модифицировал задачу автора. Я лишь указал, что мой алгоритм будет иметь линейную сложность при условии существования подходящей хэш-функции (устал это повторять). 
Доказать правильность работы алгоритма означает доказать, что он правильно находит моду. Идея алгоритма тривиальна: последовательно просматривая входной массив подсчитываем и сохраняем во вспомогательной структуре число встреч каждого элемента, следя за текущим рекордным значением. Вам действительно неочевидно, что в результате будет найдены мода? Что именно неочевидно?


Мое решение лучше тем, что для линейной асимптотики алгоритма требуются более мягкие условия (имея достаточно много оперативной памяти, я могу сделать хэш функцию со сколь угодно малой вероятностью коллизий, сделав долю "плохих" входных массивов близкой к нулю).
 

А почему вы для доказательства своей правоты увеличиваете n до бесконечности, но при этом не увеличиваете оперативку до бесконечности? 

На практике хэш - вариант бесспорно даст лучшие результаты. Потому что интересует только скорость. память докупается по необходимости. 

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

 удалено 

извиняюсь


"А почему вы для доказательства своей правоты увеличиваете n до бесконечности, но при этом не увеличиваете оперативку до бесконечности? 

На практике хэш - вариант бесспорно даст лучшие результаты. Потому что интересует только скорость. память докупается по необходимости. "



Для доказательства правоты не используют симуляция, в данном вопросе. Необходимо дать четкое формальное доказательство.

Употребление Вами слова беспорно, тут не корректно, во-первых оно не верно. Во-вторых спорно. 

Кроме того существует класс задач, для которых память критичней времени.

с ув.

 

Это сообщение отредактировал(а) esperant0 - 27.5.2006, 14:00

В таком тоне здесь никакой дисскуссии не будет.
Пожалуйста, используйте деревья.


Это по моему очевидно. А вот у дерева алгоритм линейным не получиться ни в каком случае.