Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > МОДА

Автор: Golden Hands 15.5.2006, 21:51

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

Автор: maxim1000 15.5.2006, 23:32

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

Автор: esperant0 15.5.2006, 23:57

Цитата(maxim1000 @ 15.5.2006,  23:32) мода, если мне память не изменяет, это максимум? максимум ищется за один проход (в переменной надо сохранять параметры текущего максмума) мода это элемент встечающийся максимальное число раз

Автор: Golden Hands 16.5.2006, 00:20

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

Автор: maxim1000 16.5.2006, 00:36

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

Автор: nostromo 16.5.2006, 09:10

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

Автор: maxim1000 16.5.2006, 10:50

Цитата(nostromo @  16.5.2006,  08:10 ) При обработке очередного элемента обновляем соответствующую ячейку списка  в лучшем случае на это понадобится log(n) - это если хранить в упорядоченном массиве... только тогда добавление будет дольше...

Автор: nostromo 16.5.2006, 11:26

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

Автор: Mayk 16.5.2006, 11:37

Цитата(maxim1000 @  16.5.2006,  14:50 ) в лучшем случае на это понадобится log(n) - это если хранить в упорядоченном массиве... только тогда добавление будет дольше...   Зачем в массиве?  Есть бинарное дерево поиска. Немного модифицируем - добавим в узел поле count, которое будет указывать сколько раз встречается данный элемент. Мы можем использовать добавлять элемент из массива бинарное дерево следующим образом: 1) если узла с таким элементом в дереве ещё не было, то он добавляется как в обычное бинарное дерево поиска, и node.count <- 1 2) если узел с таким элементом есть, то мы увеливаем у узла count. далее проходим по всему дереву и ищем максимум.

Автор: Golden Hands 16.5.2006, 11:42

Вот, собстно, что у меня сейчас. Кидаю паскалевский код, т.к. блок-схемы подзабыл    element - массив исходных значений, count - массив для подсчета числа вхождений элемента. Код for i:=1 to High(element) do   Begin     t:=element[i];     for k:=i to High(element) do       if t:=element[k] then count[i]:=count[i]+1;    // количество вхождений элемента   End; Flag:=False; for i:=1 to High(count) do   if count[i]<>1 then     Begin       Flag:=True;       Break;     End; if Flag=False then ShowMessage('Невозможно подсчитать моду');  //все элементы массива count равны 1 if Flag=True then <цикл определения максимального элемента count и его номера>; Есть вариант вставить цикл (между 5 и 6 строками в коде), который будет проходить по всему массиву element и разрешать выполнение (строка 6) только в том случае, если текущий элемент не входит в этот массив. Но тогда: 1) Если вхождение установится быстро, то все ОК. 2) Если вхождение установится в самом конце прохода, то получится двойная трата времени, чем было бы без проверки вхождений.

Автор: sergejzr 16.5.2006, 11:46

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

Автор: SoWa 16.5.2006, 11:51

Ну ты заврал про кол-во итераций. Их не квадрат... Цитата(Golden Hands @  16.5.2006,  11:42 ) if Flag=True then <цикл определения максимального элемента count и его номера>; Как уже предлагал Mayk, а может я не так понял, создадим новый тип, который будет хранить два значения- сама цифра и кол-во её вхождений в множество. Причем у каждого последующего элемента с одинаковой "цифрой" кол-во её вхождений будет на 1 больше. К примеру: цифра 6 встречалась два раза на момент начала действия,тогда было 6,2; Появилась еще одна шестерка. И стало 6,2; 6,3; И далее: 6,2; 6,3; 6,4; И затем просто ищи максимум среди кол-ва вхождений.

Автор: nostromo 16.5.2006, 11:53

Цитата(Mayk @ 16.5.2006,  11:37) Цитата(maxim1000 @  16.5.2006,  14:50 ) в лучшем случае на это понадобится log(n) - это если хранить в упорядоченном массиве... только тогда добавление будет дольше...   Зачем в массиве?  Есть бинарное дерево поиска. Немного модифицируем - добавим в узел поле count, которое будет указывать сколько раз встречается данный элемент. Мы можем использовать добавлять элемент из массива бинарное дерево следующим образом: 1) если узла с таким элементом в дереве ещё не было, то он добавляется как в обычное бинарное дерево поиска, и node.count <- 1 2) если узел с таким элементом есть, то мы увеливаем у узла count. далее проходим по всему дереву и ищем максимум. Поиск в бинарном дереве как раз и имеет сложность log(n)

Автор: Golden Hands 16.5.2006, 11:59

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

Автор: SoWa 16.5.2006, 12:29

НЕЕЕ. не двумерный. А вот так: Код type CF=record c: integer; count: integer; end var  mas: array[1..] of CF;

Автор: Golden Hands 16.5.2006, 13:04

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

Автор: maxim1000 16.5.2006, 13:11

Цитата(Mayk @  16.5.2006,  10:37 ) Есть бинарное дерево поиска. Цитата(nostromo @  16.5.2006,  10:53 ) Поиск в бинарном дереве как раз и имеет сложность log(n) я бы уточнил: поиск в сбалансированном бинарном дереве пропорционален log(n) в худшем случае он пропорционален n, так что придётся тратить время на балансировку ... впрочем, и быстрая сортировка в худшем случае пропорциональна n^2  если есть достаточно памяти (ещё столько ж, сколько занимает массив), то лучше сортировка слиянием - она гарантированно занимает n*log n...

Автор: Golden Hands 16.5.2006, 14:43

Проблема решена так: сортирую массив, в подцикле проверяю количество вхождений значения, при его изменении прерываю подцикл и пройденные элементы дальше не учитываю. Код g:=1; for i:=1 to High(element) do   Begin     count[i]:=0;     if g=i then       Begin         t:=element[g];         for k:=g to High(element) do           if t:=element[k] then count[i]:=count[i]+1           else             Begin               g:=k;               break;             End;        End;     <over>   End;   Временные затраты очень малы. Что и следовало...     Всех благодарю за участие!

Автор: sergejzr 16.5.2006, 14:52

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

Автор: Mayk 17.5.2006, 06:20

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

Автор: esperant0 17.5.2006, 07:25

Цитата(nostromo @ 16.5.2006,  09:10) Можно за один проход (ну почти ;) ). Постоянно храним и обновляем список встреченных значений, их текущее количество (список частот), а также индекс в списке элемента, который встретился максимальное число раз.  При обработке очередного элемента обновляем соответствующую ячейку списка частот и проверяем, не побит ли рекорд.  Можно сказать, что алгоритм работает за один проход только в случае, когда не тратится много времени на поиск нужного элемент в списке частот при обновлении. Напиример, должно хорошо работать, когда различных элементов не очень много, или на множестве элементов есть хорошая хэш-функция. 1) Во-первых, ваше "что алгоритм работает за один проход только в случае, когда"   .... неверно 2) Во-вторых в общем случае ваш алгоритм работает за х*лог х времени. с ув

Автор: esperant0 17.5.2006, 07:44

Цитата(nostromo @ 16.5.2006,  11:26) Цитата в лучшем случае на это понадобится log(n) - это если хранить в упорядоченном массиве... только тогда добавление будет дольше... Нет, вычисляем хэш от очередного числа и находим его индекс. Никакого log(n). конечно же. нет.

Автор: nostromo 17.5.2006, 14:51

Сейчас, сейчас... Критерием истины, как известно, является практика, поэтому приступим. Пусть входными элементами будут целые числа, а в качестве хэш функции возьмем остаток от деления на фиксированное число (bufSize). Список частот (currFreq) будем хранить в массиве размера bufSize. На случай коллизий, в каждом элементе currFreq будем хранить список пар (<число> @ <частота>). Программу напишем на Smalltlak (VisualWorks). В этой простой задаче обойдемся стандартной библиотекой и новых классов создавать не будем.  Собственно программа: Код bufSize := 10000. hashFunc := [:x | (x \\ bufSize) + 1].   main :=  [:input |     res := 0 @ 0.   currFreq := Array new: bufSize.   currFreq doWithIndex: [:x :i | currFreq at: i put: List new].   input do: [:x |      | ind list ind1 |     ind := hashFunc value: x.     list := currFreq at: ind.     ind1 := list findFirst: [:p | p x = x].     ind1 > 0 ifTrue: [ | nn pair | pair := list at: ind1.            nn := pair y + 1. pair y: nn.            (nn > res y) ifTrue: [res x: pair x. res y: nn. ]]         ifFalse: [ list add: x @ 1]].   res. ]. Проверяем работу: Код input := #( 5 3 6 4 5 8 7 9 6 6 7 6 3 2 1 3 5 6 7 8 9 9). main  value: input  Результат:  6@5 Действительно, число 6 встречается 5 раз, и это максимум. Проверяем зависимость вермени работы от размера входного массива, в котором записаны случайные числа. Сначала пусть случайные числа будут в диапазоне от 1 до 100 (много коллизий) Код rndGen := Random new. rnd := [(rndGen next * 100) truncated]. counts := #(2000 4000 8000 16000 32000 64000 128000 256000  512000). res := counts collect: [:nn |  input := (1 to: nn) collect: [:i | rnd value]. nn1 := 5. "количество итераций для осреднения" times := (1 to: nn1) collect: [:i | Core.Time millisecondsToRun: [main  value: input]].  r1 := (times inject: 0 into: [:r :n | r + n]) / nn1. "среднее время" r1 rounded.]. В переменной res: #(8 12 15 25 18 25 39 64 120) --- очевидно, линейный рост времени исполнения, накокого n*log(n). Теперь случай, когда случайные числа в диапазоне от 1 до 10^7 (мало коллизий): Код rndGen := Random new. rnd := [(rndGen next * 1e7) truncated]. counts := #(2000 4000 8000 16000 32000 64000 128000 256000  512000). res := counts collect: [:nn |  input := (1 to: nn) collect: [:i | rnd value]. nn1 := 5. "количество итераций для осреднения" times := (1 to: nn1) collect: [:i | Core.Time millisecondsToRun: [main  value: input]].  r1 := (times inject: 0 into: [:r :n | r + n]) / nn1. "среднее время" r1 rounded.]. В переменной res:  #(9 13 15 15 27 45 116 304 997 3613) --- в этом случае требуется заметно больше памяти (больше элементов попадает в currFreq, плюс сами числа требуют больше памяти --- Smalltalk автоматически перобразует целые числа, в первом случае они влазили в Smallint (два байта)),  поэтому линейная асимптотика для больших значений немного испорчена сборщиком мусора.  В случае асимптотики n*log(n) время на каждом шаге должно было бы вырастать в 4 раза. Добавлено @ 14:55  Небольшая поправка, в последнем тесте counts := #(1000 2000 4000 8000 16000 32000 64000 128000 256000 512000). (Не оттуда скопировал.)

Автор: sergejzr 17.5.2006, 15:19

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

Автор: nostromo 17.5.2006, 15:45

Цитата  В случае асимптотики n*log(n) время на каждом шаге должно было бы вырастать в 4 раза.  Виноват, это совсем не так. Зависимость сложнее: если 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, спасибо.

Автор: esperant0 17.5.2006, 22:55

Цитата(nostromo @ 17.5.2006,  14:51) Сейчас, сейчас... Критерием истины, как известно, является практика, поэтому приступим.   Я конечно еще раз извенюсь. Но критерием истины - является доказательство. Вы его не привели, да если често и не сможете привезти, ибо его нет. А ваше численные примеры, лишь смущают не ведующих. А на самом деле профанация чистой воды. с уважением

Автор: maxim1000 17.5.2006, 23:41

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

Автор: nostromo 18.5.2006, 09:12

Уважаемый 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, значит, сложность алгоритма --- линейная.

Автор: esperant0 18.5.2006, 20:23

Цитата(nostromo @ 18.5.2006,  09:12) Уважаемый 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 не реабельно. то есть не выполнимо в общем случае

Автор: nostromo 19.5.2006, 08:53

Цитата 1.2 не реабельно. то есть не выполнимо в общем случае Да ну? А что такое общий случай? С точки зрения практики, этот пункт один из самых легко достижимых. Могу предложить универсальный способ для любых объектов. Хэш функция выглядит следующим образом: входной объект, сериализуется в строку, вычисляеется от нее MD5-хэш, он, в свою очередь, берется по модулю параметра K. Все. Настройка хэш функции, осуществляемая в секции инициализации алгоритма, заключается в установке значения K, например, равным числу элементов входного массива.  Здесь скорее проблема придумать хороший контрпример. Предложенный алгоритм поиска моды имеет линейную сложность (от размера входного массива) и в теории и на практике (пока хватает оперативной памяти), а Вы, кажется, просто не хотите это признать. Добавлено @ 09:02  Если подходить совсем строго, с теоретической точки зрения для любого произвольного входного массива, о котором вообще ничего не известно, кроме числа элементов, действительно нельзя гарантированно предложить хэш функцию с малым число коллизий. Однако на практике, это почти всегда возможно, плюс, с самого начала я говорил, что алгоритм имеет линейную сложность при условии существования "хорошей" хэш-функции.

Автор: esperant0 19.5.2006, 15:47

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

Автор: nostromo 19.5.2006, 16:11

Цитата Обычно алгоритмы оценивают, с точки зрения худшего случая. В худшем случае ваш алгоритм не линейный. Значит, быстрая сортировка имеет асимптотику n^2? На множестве входных массивов, для которых есть возможность выбора "хорошей" хэш функции алгоритм получается линейный. Мне показалось, Вы с этим спорили. P.S. Кажется, пора закругляться.

Автор: esperant0 19.5.2006, 16:24

Ассимптотика и худший случай разные вещи. худший случай вероятностного алгоритма быстрой сортировки п^2 но вероятность этого случая не зависит от распределения входных данных и экспоненциально мала от п. В вашем же случае худший случай есть и для определенного вида данных. Ваш алгоритм не линейный. резюмы: вы решили не задачу автора, а модифицировали задачу, дополнив ее некоторым ограничением. Кроме, того вы так и не привели докозательство правильности работы. Вот решение аналогичное вашему. Предположим что для исходного массива выполнены условия применения ведерной-сортировки (backet sorting) отсортируем массив за линейное время и найдем в нем моду. Это решение не хуже и не лучше вашего. Правда оно лучше тем, что док-во его правильности более прозрачно. с ув.

Автор: nostromo 19.5.2006, 17:07

Цитата В вашем же случае худший случай есть и для определенного вида данных. Ваш алгоритм не линейный. Этого не понял, какой-такой плохой вид данных? Укажите пожалуйста, какой пункт http://forum.vingrad.ru/index.php?showtopic=96244&view=findpost&p=735128, кроме перебора значений входного массива требует времени, зависящего от N. По поводу пункта 1.2 я уже ответил. Цитата резюмы: вы решили не задачу автора, а модифицировали задачу, дополнив ее некоторым ограничением. Кроме, того вы так и не привели докозательство правильности работы. В чем я модифицировал задачу автора. Я лишь указал, что мой алгоритм будет иметь линейную сложность при условии существования подходящей хэш-функции (устал это повторять).  Доказать правильность работы алгоритма означает доказать, что он правильно находит моду. Идея алгоритма тривиальна: последовательно просматривая входной массив подсчитываем и сохраняем во вспомогательной структуре число встреч каждого элемента, следя за текущим рекордным значением. Вам действительно неочевидно, что в результате будет найдены мода? Что именно неочевидно? Цитата Вот решение аналогичное вашему. Предположим что для исходного массива выполнены условия применения ведерной-сортировки (backet sorting) отсортируем массив за линейное время и найдем в нем моду. Это решение не хуже и не лучше вашего. Правда оно лучше тем, что док-во его правильности более прозрачно. Мое решение лучше тем, что для линейной асимптотики алгоритма требуются более мягкие условия (имея достаточно много оперативной памяти, я могу сделать хэш функцию со сколь угодно малой вероятностью коллизий, сделав долю "плохих" входных массивов близкой к нулю).

Автор: sergejzr 26.5.2006, 12:37

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

Автор: nostromo 26.5.2006, 12:58

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

Автор: esperant0 27.5.2006, 08:12

удалено  извиняюсь "А почему вы для доказательства своей правоты увеличиваете n до бесконечности, но при этом не увеличиваете оперативку до бесконечности?  На практике хэш - вариант бесспорно даст лучшие результаты. Потому что интересует только скорость. память докупается по необходимости. " Для доказательства правоты не используют симуляция, в данном вопросе. Необходимо дать четкое формальное доказательство. Употребление Вами слова беспорно, тут не корректно, во-первых оно не верно. Во-вторых спорно.  Кроме того существует класс задач, для которых память критичней времени. с ув.

Автор: sergejzr 27.5.2006, 12:59

В таком тоне здесь никакой дисскуссии не будет. Пожалуйста, используйте деревья. Цитата(nostromo @  19.5.2006,  14:11 ) На множестве входных массивов, для которых есть возможность выбора "хорошей" хэш функции алгоритм получается линейный. Это по моему очевидно. А вот у дерева алгоритм линейным не получиться ни в каком случае.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)