|
|
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Также хочу добавить, что первое дерево при добавлении отрезков необходимо делать наиболее эффективным. Т.е., если получилось так, что первое дерево содержит отрезки (a1,b1) и (a2,b2), и вот добавляется отрезок (a1,b2) (или чуть шире, но не пересекаясь с существующими отрезками в этом дереве). Тогда для устранения "провала" между b1 и а2 новый отрезок вносим в первое дерево, а отрезки (a1,b1) и (а2,b2) убираем куда-нибудь подальше (пытаемся встраивать в последующие деревья или, быть может, заводим новые). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 15:29:08 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
По моему, эта задача уже решена (в общем случае) Гуттманом путем построения специального вида дерева (R-Tree) для индексации и быстрого поиска пространственных данных. Однако для наихудшего случая, логарифмическое время не гарантируется, поэтому здесь нужна дополнительная информация. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 16:03:15 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
Спаибо большое за идею!!! : regom Все отрезки рассматривал как лес деревьев, в каждом из которых отрезки не пересекаются и .... Можно организовать список массивов (лес массивов) каждый массив хранит упорядоченные координаты концов отрезков, отрезки из 1 массива-непересекаются. Таким образом, каждый из массивов может содержать не более 1 искомого отрезка. И по каждому из таких массивов можно осуществить бинарный поиск. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 16:04:20 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
алчностьСпаибо большое за идею!!! тьфу Спасибо :) Сомниваюсь, что решение с деревьями будет более оптимальным(чисто интуитивно) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 16:09:41 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
алчностьСомниваюсь, что решение с деревьями будет более оптимальным(чисто интуитивно) А зря. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 16:39:31 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
maytonалчностьСомниваюсь, что решение с деревьями будет более оптимальным(чисто интуитивно) А зря. Интересно, а в чём смысл?(в 2-х словах) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.12.2008, 16:58:24 |
|
||
|
Изучение трудов Кнута (Как изучать)
|
|||
|---|---|---|---|
|
#18+
алчность, > Имеется множество одномерных отрезков вида: (x_left,x_right). > Требуется так организовать это множество (список), чтобы для заданного x > временная сложность поиска отрезка, удовлетворяющего условию x_left<x< x_right > в большинстве случаев была меньше O(n), > где n- количество отрезков. у тебя имелись в виду одни требования, но в постановке задачи они не отражены. Очевидно ты имел в виду что требуется уметь еще и быстро добавлять/удалять новые отрезки. Но ты это не написал. Если быстро добавлять/удалять новые отрезки не нужно, то решение двольно очевидно -- просто бинарное дерево из всех концов отрезков, а в каждом узле сохраняешь информацию о тех отрезках которые "контролируют" данный участок. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.01.2009, 20:52:38 |
|
||
|
|
start [/forum/topic.php?fid=16&gotonew=1&tid=1344725]: |
0ms |
get settings: |
9ms |
get forum list: |
17ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
66ms |
get topic data: |
12ms |
get first new msg: |
7ms |
get forum data: |
3ms |
get page messages: |
61ms |
get tp. blocked users: |
2ms |
| others: | 208ms |
| total: | 391ms |
| 0 / 0 |
