SoWa, начну с реализации твоей идеи. 

я бы уточнил: поиск в сбалансированном бинарном дереве пропорционален log(n)

в худшем случае он пропорционален n, так что придётся тратить время на балансировку
...
впрочем, и быстрая сортировка в худшем случае пропорциональна n^2 

если есть достаточно памяти (ещё столько ж, сколько занимает массив), то лучше сортировка слиянием - она гарантированно занимает n*log n... 

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

 

Временные затраты очень малы. Что и следовало...    

Всех благодарю за участие! 

Это сообщение отредактировал(а) Golden Hands - 16.5.2006, 14:51

С вариантом nostromo, будет значительно быстрее. 

Добавление в отсортированный массив занимает в худшем случае линейное время.
(дан массив (2,3,4,5). Для того чтобы добавить в него 1 понадобится скопировать ВЕСЬ массив).
В случае сбалансированного(как справедливо отметили выше) бинарного дерева добавление возможно за log(n) 
  

Это сообщение отредактировал(а) Mayk - 17.5.2006, 06:21

1) Во-первых, ваше "что алгоритм работает за один проход только в случае, когда"   .... неверно


2) Во-вторых в общем случае ваш алгоритм работает за х*лог х времени.


с ув 

конечно же. нет. 

Сейчас, сейчас...

Критерием истины, как известно, является практика, поэтому приступим.

Пусть входными элементами будут целые числа, а в качестве хэш функции
возьмем остаток от деления на фиксированное число (bufSize).
Список частот (currFreq) будем хранить в массиве размера bufSize.
На случай коллизий, в каждом элементе currFreq будем хранить список пар
(<число> @ <частота>).

Программу напишем на Smalltlak (VisualWorks). В этой простой задаче обойдемся стандартной библиотекой и новых классов создавать не будем. 

Собственно программа:


Проверяем работу:


Проверяем зависимость вермени работы от размера входного массива,
в котором записаны случайные числа.
Сначала пусть случайные числа будут в диапазоне от 1 до 100 (много коллизий)

--- очевидно, линейный рост времени исполнения, накокого n*log(n).

Теперь случай, когда случайные числа в диапазоне от 1 до 10^7 (мало коллизий):

--- в этом случае требуется заметно больше памяти (больше элементов попадает в currFreq, плюс сами числа требуют больше памяти --- Smalltalk автоматически перобразует целые числа, в первом случае они влазили в Smallint (два байта)), 
поэтому линейная асимптотика для больших значений немного испорчена сборщиком мусора. 
В случае асимптотики n*log(n) время на каждом шаге должно было бы
вырастать в 4 раза.

Добавлено @ 14:55 
Небольшая поправка, в последнем тесте
counts := #(1000 2000 4000 8000 16000 32000 64000 128000 256000 512000).
(Не оттуда скопировал.) 

nostromo, отлично, только надо учесть негативные числа в хэш-функции (то есть брать |х| ) 

Виноват, это совсем не так. Зависимость сложнее:
если n пробегает ряд
(2 4 8 16 32 64 128 256  512),
то n*log(n) пробегает ряд: 
(2 8 24 64 160 384 896 2048 4608).

Отсюда следует, что в случае, если алгоритм с линейной сложностью имеет большой константный множитель по сравнению с алгоритмом с асимптотикой n*log n, то последний может оказаться предпочтительнее для довольно широкого диапазона значений (логарифм очень медленно растет). Однако подозреваю, что в рассматриваемой задаче линейный алгоритм лучше.

Добавлено @ 15:48 
sergej.z, спасибо.  

Я конечно еще раз извенюсь.

Но критерием истины - является доказательство. Вы его не привели, да если често и не сможете привезти, ибо его нет.

А ваше численные примеры, лишь смущают не ведующих. А на самом деле профанация чистой воды.


с уважением 

сложность поиска по хешу - вопрос интересный
это как раз тот случай, когда целесообразность анализа "при достаточно больших n" можно поставить под сомнение

если исследовать поведение хеша при n->oo, то он принципиально ничем не отличается от того же бинарного дерева (только у узлов там не два, а куча потомков, да и уже на втором уровне деревянная структура может не сохраняться), а значит поиск по хешу ("хорошему" хешу, что эквивалентно сбалансированности дерева) будет занимать log n (да и то, это если на втором уровне не делать чего-то типа списка/массива)

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

Это сообщение отредактировал(а) maxim1000 - 17.5.2006, 23:43

Уважаемый esperant0, по-видимому, наши разногласия связаны с различным пониманием постановки задачи, что верно заметил maxim1000.

Еще раз попробую внести ясность.

1. На вход алгоритма поступет массив M из N элементов.
2. Допущения:
    1.1. Оперативной памяти всегда достаточно, сборкой мусора, особенностями операционной системы и другими внешними факторами пренебрегаем.
    1.2. Всегда есть возможность за фиксированное время в зависимости от N настроить парметры хэш-функции так, чтобы она выдавала значения от 1 до некоторого N1 (также зависящего от N) с пренебрежимо малым числом коллизий.
    1.3. Выделение памяти под вспомогательный N1-элементный список частот занимает фиксированное время, не зависящее от N1 (или зависящее пренебрежимо слабо).
    1.4. Доступ к элементу массива (или списка) по его индексу всегда занимает фиксированное время.
3. Алгоритм.
    3.1. Инициализация. Выбирается хэш функция, со свойствами, описанными в 1.2 и создается список частот M1 размера N1. (В списке частот хранится текущее количество встреч элементов.) Инициализируются переменные для значения элемента, который встречается максимальное число раз и частота его встречи (нулем).
    3.2. Последовательно в цикле перебираются элементы входного массива M 
и для каждого из них выполняются следующие действия.
        3.2.1. С помощью хэш функции вычисляется индекс элемента в списке частот.
        3.2.1. По индексу находится элемент списка частот и инкрементируется значение текущего числа встреч элемента. (Выполнение этого пункта занимает фиксированное время --- это следует из предположения о пренебрежимо малом числе коллизий хэш функции.)
        3.2.3. Проверяется, не превосходит ли число встреч текущего элемента рекордного значения и, если превосходит, рекордное значение обновляется.
4. Очевидно, что при указанных допущениях, от размера входного массива зависит только число итераций цикла --- оно совпадает с N, значит, сложность алгоритма --- линейная.
 

1.2 не реабельно. то есть не выполнимо в общем случае 

Да ну? А что такое общий случай?

С точки зрения практики, этот пункт один из самых легко достижимых.
Могу предложить универсальный способ для любых объектов.
Хэш функция выглядит следующим образом:
входной объект, сериализуется в строку, вычисляеется от нее MD5-хэш,
он, в свою очередь, берется по модулю параметра K. Все.
Настройка хэш функции, осуществляемая в секции инициализации алгоритма, заключается в установке значения K, например, равным числу элементов входного массива. 
Здесь скорее проблема придумать хороший контрпример.

Предложенный алгоритм поиска моды имеет линейную сложность (от размера входного массива) и в теории и на практике (пока хватает оперативной памяти), а Вы, кажется, просто не хотите это признать.

Добавлено @ 09:02 
Если подходить совсем строго, с теоретической точки зрения для любого произвольного входного массива, о котором вообще ничего не известно, кроме числа элементов, действительно нельзя гарантированно предложить хэш функцию с малым число коллизий. Однако на практике, это почти всегда возможно, плюс, с самого начала я говорил, что алгоритм имеет линейную сложность при условии существования "хорошей" хэш-функции.