crazy people

[109]

ну ни фига ж себе так, ни с того ни с сего. чуваку, открывшему для себя деревья объяснил, что такое big-O notation и порекомендовал два более эффективных алгоритма. полчаса писал, наверное; даже в гуголь сходил освежить воспоминания о скиплистах. а в ответ получил:

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

ну и коммент мой он стёр, конечно. а производил впечатление совершенно нормального человека. не знаю, что и думать. неужели от кого угодно можно чего угодно ожидать?

Comments

[sply.livejournal.com]

второй предельный случай - это какой? первый - понятно, короткие паттерны. Но он не O(N^2), а O(N)

вообще, так и не понятно, откуда вы берете O(N^2). Видимо, все то же множество всех подсток T, длиной от 0 до N. Но оно здесь совершенно не нужно. Если даже и выбрать бессмысленный вариант с отдельными хэш-таблицами для каждой длины паттетна, то число таких таблиц равно кол-ву различных длин паттаров (для паттернов 'a', 'ab', 'cdef' - 3 таблицы) и число подстрок из T, которые мы будем искать в хэш-таблицах, начинающихся с позиции i (для всех 0<i<N)) будет не N, а 3. Поэтому квадрата нет, есть только O(N*3). И если длина Т составит 100, то мы проверим не 10000 подстрок, а 300. Если вы настаиваете на квадрате, объясните, пожалуйста, сами, откуда он может взяться.