Скачать: CL | DM;

Пятничные задачки для программистов.   Найти похожие ветки 

← →
TUser ©   (2006-05-02 11:56) [40]

Я тоже не знаю. Есть алгоритм Укконена, который позволяет строить суффиксное дерево за линейное время. А обход дерева, вроде бы, должен занимать как раз N log N, т.к. логарифм - это средняя высота листа, а всего листьев - O(N). Только вот не уверен.

Квадратичный алгоритм :))

for i:=0 to high do
 sum := 0
 for j:=i to high do
   sum += A[j]
   if sum = WhatWeNeed then
     returm i, j

---

← →
MBo ©   (2006-05-02 12:37) [41]

>TUser ©   (02.05.06 11:56) [40]
Можно и несколько другим квадратичным алгоритмом воспользоваться:
Построить массив частичных сумм за линейное время
s[0]=A[0]
s[i] = s[i-1]+A[i]
Затем квадратичная часть - сравнение разностей s[i]-s[j] c искомой суммой.

Отсюда осталась пара шагов модификации до NlogN...

---

Страницы: 1 2 вся ветка

Скачать: CL | DM;



Память: 0.51 MB
Время: 0.041 c