Вниз
Скачать: 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.038 c
15-1146548704
nopox
2006-05-02 09:45
2006.05.28
Доброго времени суток, Уважаемые! Простите за банальный вопрос,


2-1147329642
zorik
2006-05-11 10:40
2006.05.28
Как выделить в Екселе лист по его названию?


4-1141399908
Handle
2006-03-03 18:31
2006.05.28
Как завершить системныЙ процесс?


1-1145520148
tytus
2006-04-20 12:02
2006.05.28
Как в ListBox-e нарисовать изображение?


15-1146229579
Alex7
2006-04-28 17:06
2006.05.28
Windows XP-панель задач




   Наверх