|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Goldobin 2:5020/400 11 Aug 2003 15:24:57
To : Andrew Lazarev
Subject : Re: найти повторяющиеся элементы
--------------------------------------------------------------------------------
Hi!
> > "наиболее" быстро надо подбирать для конкретного частного случая, в
> > зависимости от свойств строк. А "более-менее" быстро - для каждой новой
> > строки считать какой-нибудь хэш и сравнивать строку только с теми ранее
> > обработанными строками, которые имеют тот же хэш. Подбирать необходимый
> > баланс между скоростью подсчета хэша, его равномерностью и его
> разрядностью.
>
> И в случае 3000 равных строк алгорит будет O(N^2*Len).
> Данный метод хорош только когда кол-во повторяющихся элементов не может
> быть порядка кол-ва элементов.
Hу дак я же и сказал "более-менее", универсальный, а это частный случай. Тем
более в данном случае будет всего максимум в два раза дольше теоретического
предела. Ведь каждую строку по крайней мере один раз надо обязательно всю
посимвольно просмотреть, для того чтобы убедиться что она полностью
совпадает? Hу тут еще один раз ее надо просмотреть для подсчета хэша,
возможно не всю. И откуда кстати O(N^2*Len)? По-моему O(N*Len) - я же каждую
новую строку сравниваю всего с _одной_ из предыдущих, коли они все
одинаковые.
Bye.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
