Сделал на раз - цикл до x + вложенный цикл. Количество итераций = sum[x], которое при x=3000 в моем случае совершенно неприемлимо. Подскажите алгоритм, определяющий моду за один проход.  

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

мода, если мне память не изменяет, это максимум?
максимум ищется за один проход (в переменной надо сохранять параметры текущего максмума) 

мода это элемент встечающийся максимальное число раз 

Мода возвращает наиболее часто встречающееся значение в массиве данных. Причем:
1) Если массив не содержит одинаковых значений, мода не может быть подсчитана.
2) Если несколько значений встречаются одинаковое число раз, мода равна тому значению, которое встречается первым. 

Аааа... я почему-то подумал, что у нас уже массив вероятностей...

Добавлено @ 00:38 
можно попробовать так:
1. сортируем массив - log(n)*n
2. идём по нему, считая длину непрерывной последовательности элементов и сравнивая с наиболее длинной из ранее встреченных 

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

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

в лучшем случае на это понадобится log(n) - это если хранить в упорядоченном массиве... только тогда добавление будет дольше... 

Нет, вычисляем хэш от очередного числа и находим его индекс. Никакого log(n). 

Зачем в массиве?  Есть бинарное дерево поиска. Немного модифицируем - добавим в узел поле count, которое будет указывать сколько раз встречается данный элемент.

Мы можем использовать добавлять элемент из массива бинарное дерево следующим образом:
1) если узла с таким элементом в дереве ещё не было, то он добавляется как в обычное бинарное дерево поиска, и node.count <- 1
2) если узел с таким элементом есть, то мы увеливаем у узла count.


далее проходим по всему дереву и ищем максимум.

 

Вот, собстно, что у меня сейчас. Кидаю паскалевский код, т.к. блок-схемы подзабыл   


element - массив исходных значений, count - массив для подсчета числа вхождений элемента.




Есть вариант вставить цикл (между 5 и 6 строками в коде), который будет проходить по всему массиву element и разрешать выполнение (строка 6) только в том случае, если текущий элемент не входит в этот массив. Но тогда:
1) Если вхождение установится быстро, то все ОК.
2) Если вхождение установится в самом конце прохода, то получится двойная трата времени, чем было бы без проверки вхождений.  

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

если min/max числа в разумных пределах, можно прямо таблицу составить, где индекс - само число. при каждом последующем числе х увеличиваем на еденицу значение массив[х] и сравниваем с МОД'ом из предидущей итерации.
(В принципе тот же хэш, предложенный nostromo, хо с функцией hash(x)=x) 

Ну ты заврал про кол-во итераций. Их не квадрат...

Как уже предлагал Mayk, а может я не так понял, создадим новый тип, который будет хранить два значения- сама цифра и кол-во её вхождений в множество. Причем у каждого последующего элемента с одинаковой "цифрой" кол-во её вхождений будет на 1 больше. К примеру: цифра 6 встречалась два раза на момент начала действия,тогда было
6,2;
Появилась еще одна шестерка. И стало
6,2;
6,3;
И далее:
6,2;
6,3;
6,4;
И затем просто ищи максимум среди кол-ва вхождений. 

Поиск в бинарном дереве как раз и имеет сложность log(n) 

SoWa, двумерный масив предлагаешь? Я обдумывал это, сейчас еещ прикину. 

НЕЕЕ. не двумерный. А вот так: