Если я правильно понял, задача в следующем:
N векторов, образующих замкнутую цепочку (конец первого совпадает с началом второго, конец второго — с началом третьего и т.д., а конец N-го — с началом 1-го), помещают в массив, перемешав.
Надо восстановить последовательность векторов в массиве, при которой они вновь образуют замнутую цепь. Алгоритм должен иметь сложность O(2*N).

Здравствуйте, Forrest_Gump, Вы писали:

F_G>Если я правильно понял, задача в следующем:
F_G>N векторов, образующих замкнутую цепочку (конец первого совпадает с началом второго, конец второго — с началом третьего и т.д., а конец N-го — с началом 1-го), помещают в массив, перемешав.
F_G>Надо восстановить последовательность векторов в массиве, при которой они вновь образуют замнутую цепь. Алгоритм должен иметь сложность O(2*N).

Замечание: оценка дурацкая какая-то не бывает. Бывает O(N).

Как я понимаю элемент массива это скажем 2 пары координат (для простоты возьмём одномерную картину, алгоритму плевать, а нам проще, итого 2 числа).

Было

4 3
2 4
3 1
1 2

Надо иметь в конце массив вида.

1 2
2 4
4 3
3 1

Так? Продолжаем думать

Предположим что в изначальном массиве ориентация векторов сохранена (а то вообще блин бардак)

Ограничения на память не было Пусть у нас координаты от 1 до N.
Заведём массив A размера N. Пройдёмся по всем элементам массива векторов и будем в ячейку с номером равным элементу слева записывать значение равное элементу справа.
Пример.
Исходный массив

1 3
2 4
5 2
4 1
3 5

Запишем :
в ячёйку 1 число 3
в ячейку 2 число 4
в ячейку 5 число 2
в ячейку 4 число 1
в ячейку 3 число 5
И получим такое

3
4
5
1
2

На это надо порядка N операций.
Что дальше? Дальше выписываем новый массив
Пишем
1 и число которое было в ячейке 1 (обозначим его A[1])
A[1] и число которое было в ячейке A[1] (обозначим его A[2])
A[2] и число которое было в ячейке A[2] (обозначим его A[3])
A[3] и число которое было в ячейке A[3] (обозначим его A[4])
A[4] и число которое было в ячейке A[4]
Получим

1 3
3 5
5 2
2 4
4 1

Затратили мы на это порядка N операций
Итого, всего порядка N операций.
Если координаты не одномерные, то можно, совершив ещё один проход, ввести над ними функцию. которая отбразит их на что-то одномерное. Но ИМХО задача стояла именно так как я догадался

Здравствуйте, Forrest_Gump, Вы писали:

F_G>Если я правильно понял, задача в следующем:
F_G>N векторов, образующих замкнутую цепочку (конец первого совпадает с началом второго, конец второго — с началом третьего и т.д., а конец N-го — с началом 1-го), помещают в массив, перемешав.
F_G>Надо восстановить последовательность векторов в массиве, при которой они вновь образуют замнутую цепь. Алгоритм должен иметь сложность O(2*N).

Можно за O(1)?
Сначала определимся с условием. Вектор — множество направленных отрезков (по определению), а в условии нам как раз даны вектора. Т.к. изначальные вектора образуют замкнутую цепочку, то их сумма равна 0. Несложно видеть, что в каком бы порядке мы эти вектора не взяли, они будут образовывать замкнутую цепочку. Т.е. выдаем как ответ данную нам последовательность

Видимо в условии имелись ввиду именно направленные отрезки, а не вектора. Для них, если нет ограничения на память, решение уже привел adontz. Внесу свои три копейки. Решение в среднем за O(N) с использованием дополнительной памяти O(N).

Построим хеш-таблицу для начал отрезков. Найдем в этой таблице отрезок с началом, совпадающим с концом 1го отрезка. Заменим эти два отрезка на один "виртуальный". Повторим пока не останется один отрезок (причем, это будет отрезок нулевой длины).

Замечу, что решение adontz предполагает, что не существует двух отрезков с одним началом. Однако, об этом ничего не говорилось в условии. Мое решение легко переделывается на этот случай применением эвристики сжатия путей и весовой эвристики (это сложившийся у нас сленг, не помню как это по-научному называется). О том, что это такое, можно прочесть в Кормане. Сложность также останется с среднем O(N).

P.S. Решение adontz тоже легко переделывается на этот случай.

Здравствуйте, Tan4ik, Вы писали:

T>Сначала определимся с условием. Вектор — множество направленных отрезков (по определению)
Вектор — направленный отрезок (ОДИН) — по определению

Здравствуйте, adontz, Вы писали:

A>Предположим что в изначальном массиве ориентация векторов сохранена (а то вообще блин бардак)
Не понял ? А как иначе-то ? (В смыле — как может быть не сохранена ориентация вектора в пространстве, если он задаётся своими координатами ?)

A>Ограничения на память не было Пусть у нас координаты от 1 до N.
А если — от 745 до 8567 ?

A>Заведём массив A размера N. Пройдёмся по всем элементам массива векторов и будем в ячейку с номером равным элементу слева записывать значение равное элементу справа.
А если координаты вершин — не натуральные числа ?

В общем, я не понял, как распространить этот специальный случай на общий

Здесь мне предложили такое решение:

О(2*N) не бывает. О() съедает константы. Т.е. O(2*n)==О(N).
Я так понял, что каждый вектор имеет координаты начала и конца.
За О(N) сделать просто. Заведем К-мерный массив векторов (в нормальном понимании, т.е. только координаты конца), где К — размерность вектора. Если на плоскости, то К=2. Массив такой, что бы все вектора помещались в этот "паралепипед". (Это в надежде, что координаты векторов целочисленные). Далее, для каждого вектора положим в ячейку массива с координатами начала координаты конца. Далее, хватаем любой вектор и начинаем заполнять массив, т.к. координаты конца дадут координаты начала какого-то вектора. Продолжаем обход, пока не вернемся в начальную точку.

Я так понял, что это фактически — решение, предложенное adontz, но распространённое на более общий случай.

Теперь мои вопросы и замечания:
Пусть, в самом деле, координаты — целые числа. (Спрошу у того, кто сказал мне эту задачу.)
Однако, их значения могут быть, например, {0,1}, {1,0}, {1,1}, {1,2}, {1,3}, {10000, 10000} (указал только координаты начал двумерных векторов). Итого — всего 6 векторов.
Если теперь создавать двумерный массив структур типа такого

typedef struct{
   int x;
   int y;
}Point2D;
 
Point2D pointsArray[10000][10000];

то это будет, мягко говоря, неэкономично с точки зрения памяти

Как решается такая проблема ?
Можно ли здесь как-то применить хэш-таблицы. (Я плохо представляю, что это такое , но посмотрю обязательно

Здравствуйте, Forrest_Gump, Вы писали:

F_G>Как решается такая проблема ?
F_G>Можно ли здесь как-то применить хэш-таблицы. (Я плохо представляю, что это такое , но посмотрю обязательно

Эпиграф:
Как физик кипятит чайник воды?
Наливает воду в чайник, ставит на плиту, зажигает и ждёт когда закипит.
Как математик кипятит чайник воды?
Наливает воду в чайник, ставит на плиту, зажигает и ждёт когда закипит.
Как физик кипятит чайник воды, который уже полный?
Ставит на плиту, зажигает и ждёт когда закипит.
Как математик кипятит чайник воды, который уже полный?
Вывивает воду чем сводит задачу к предыдущей.

Думаю не надо здесь искать нового решения.
Можно сделать так. составить таблицу соответствия реальных координат натуральным числам. Так как нам абсолютно плевать как они друг другу соответствуют, лишь бы однозначно, думаю при некоторой сноровке и эту задачу можно решить за O(N), хотя возможно потребуется не один проход.

Здравствуйте, Tan4ik, Вы писали:


T>Построим хеш-таблицу для начал отрезков. Найдем в этой таблице отрезок с началом, совпадающим с концом 1го отрезка. Заменим эти два отрезка на один "виртуальный". Повторим пока не останется один отрезок (причем, это будет отрезок нулевой длины).

Это всё за O(1)

T>Замечу, что решение adontz предполагает, что не существует двух отрезков с одним началом.

Можно в ячейках второго массива хранить список вершин. Но с другой стороны мы тогда теряем однозначность восстановления цепочки. Да и петелька это уже, а не цепочка

Здравствуйте, adontz, Вы писали:


A>Можно сделать так. составить таблицу соответствия реальных координат натуральным числам. Так как нам абсолютно плевать как они друг другу соответствуют, лишь бы однозначно, думаю при некоторой сноровке и эту задачу можно решить за O(N), хотя возможно потребуется не один проход.

Хорошо, пусть вектора на плоскости и всего K разных координат (и по X, и по Y — просто K разных чисел).
Выходит, что для решения задачи надо построить дополнительный массив K*K ?

Тем самым, как я понял, решается проблема в примере с {0,1}, {1,0}, {1,1}, {1,2}, {1,3}, {10000, 10000}:
не надо массив 10000x10000, достаточно 4x4 — неплохая экономия

Всем огромное спасибо и с Новым годом

Если будут другие варианты решений, с удовольствием выслушаю

Здравствуйте, Forrest_Gump, Вы писали:

F_G>Тем самым, как я понял, решается проблема в примере с {0,1}, {1,0}, {1,1}, {1,2}, {1,3}, {10000, 10000}:
F_G>не надо массив 10000x10000, достаточно 4x4 — неплохая экономия

Нет не так.
Например такой алгоритм. Ищем максимумыи минимумы по всем координатам.
Для X это 10000 и 0
Для Y это 10000 и 0
Далее вводим функцию отображения в одномерное пространство
Z = (x — minX) * (maxY — minY) + Y;
Получится

{    0,     1} -     1
{    1,     2} - 10002
{    1,     0} - 10000
{    1,     1} - 10001
{    1,     3} - 10003
{10000, 10000} - 20000

Далее отображаем получившиеся числа на натуральные

    1 - 1
10002 - 2
10000 - 3
10001 - 4
10003 - 5
20000 - 6

И получим вот это

{    0,     1} - 1
{    1,     2} - 2
{    1,     0} - 3
{    1,     1} - 4
{    1,     3} - 5
{10000, 10000} - 6

Итого нужен одномерный массив размера 6.

Здравствуйте, adontz, Вы писали:

F_G>>Тем самым, как я понял, решается проблема в примере с {0,1}, {1,0}, {1,1}, {1,2}, {1,3}, {10000, 10000}:
F_G>>не надо массив 10000x10000, достаточно 4x4 — неплохая экономия

A>Нет не так.
A>Например такой алгоритм. Ищем максимумыи минимумы по всем координатам.
A>Для X это 10000 и 0
A>Для Y это 10000 и 0
A>Далее вводим функцию отображения в одномерное пространство
A>Z = (x — minX) * (maxY — minY) + Y;
A>Получится

A>

A>{    0,     1} -     1
A>{    1,     2} - 10002
A>{    1,     0} - 10000
A>{    1,     1} - 10001
A>{    1,     3} - 10003
A>{10000, 10000} - 20000
A>

A>Далее отображаем получившиеся числа на натуральные

A>

A>    1 - 1
A>10002 - 2
A>10000 - 3
A>10001 - 4
A>10003 - 5
A>20000 - 6
A>

A>И получим вот это

A>

A>{    0,     1} - 1
A>{    1,     2} - 2
A>{    1,     0} - 3
A>{    1,     1} - 4
A>{    1,     3} - 5
A>{10000, 10000} - 6
A>

A>Итого нужен одномерный массив размера 6.

Тут ты подразумеваешь сортировку, т.е. сложность становится O(N*log(N)). А в условии просилось O(N).

Здравствуйте, adontz, Вы писали:


T>>Построим хеш-таблицу для начал отрезков. Найдем в этой таблице отрезок с началом, совпадающим с концом 1го отрезка. Заменим эти два отрезка на один "виртуальный". Повторим пока не останется один отрезок (причем, это будет отрезок нулевой длины).

A>Это всё за O(1)

За O(N). То было шуткой.

T>>Замечу, что решение adontz предполагает, что не существует двух отрезков с одним началом.

A>Можно в ячейках второго массива хранить список вершин. Но с другой стороны мы тогда теряем однозначность восстановления цепочки. Да и петелька это уже, а не цепочка

См. P.S.

Здравствуйте, Forrest_Gump, Вы писали:

F_G>Здравствуйте, Tan4ik, Вы писали:

T>>Сначала определимся с условием. Вектор — множество направленных отрезков (по определению)
F_G>Вектор — направленный отрезок (ОДИН) — по определению
Только не надо флейма по этому поводу. Большенство ученых сходятся на том, что вектор — множество направленных отрезков. Хотя я видел определения вектора как ОДИН направленный отрезок. В этом случае определения всяких произведений (скалярных, векторных) и т.п. выглядят просто уродливо.

Здравствуйте, Tan4ik, Вы писали:
F_G>>Здравствуйте, Tan4ik, Вы писали:

T>Только не надо флейма по этому поводу. Большенство ученых сходятся на том, что вектор — множество направленных отрезков. Хотя я видел определения вектора как ОДИН направленный отрезок.
Ты в школе учился вообще ?
В какой ? (Я тоже из Саратова )

Здравствуйте, Tan4ik, Вы писали:

T>Тут ты подразумеваешь сортировку, т.е. сложность становится O(N*log(N)). А в условии просилось O(N).

Где сортировка?

Здравствуйте, Forrest_Gump, Вы писали:

T>>Только не надо флейма по этому поводу. Большенство ученых сходятся на том, что вектор — множество направленных отрезков. Хотя я видел определения вектора как ОДИН направленный отрезок.
F_G>Ты в школе учился вообще ?
F_G>В какой ? (Я тоже из Саратова )
ЛКПН (нынче просто ЛПН)

Здравствуйте, Forrest_Gump, Вы писали:

FG> Здравствуйте, Tan4ik, Вы писали:
FG> F_G>>Здравствуйте, Tan4ik, Вы писали:
FG>
T>> Только не надо флейма по этому поводу. Большенство ученых сходятся на
T>> том, что вектор — множество направленных отрезков. Хотя я видел
T>> определения вектора как ОДИН направленный отрезок.
FG> Ты в школе учился вообще ?
FG> В какой ? (Я тоже из Саратова )

Привет землякам!!!

-- Всего хорошего!
-- Alex Alexandrov, e-mail: alex_alexandrov@fromru.com

Привет. Задача не решаема за O(N), т.к. для поиска следующего вектора в худшем случае нужно log2(N) операций, естественно при предварительном создании отсортированного массива начал векторов — O(N*log2(N)). В сумме получаем O(2*N*log2(N)) == O(N*log2(N)). Хэш таблица не поможет — в худшем случае она может выродится и потребуется N операций для поиска — получаем O(N*N). Такае-же сложность и при поиске в лоб.

Здравствуйте, Forrest_Gump, Вы писали:

F_G>Здравствуйте, adontz, Вы писали:

A>>Предположим что в изначальном массиве ориентация векторов сохранена (а то вообще блин бардак)
F_G>Не понял ? А как иначе-то ? (В смыле — как может быть не сохранена ориентация вектора в пространстве, если он задаётся своими координатами ?)

A>>Ограничения на память не было Пусть у нас координаты от 1 до N.
F_G>А если — от 745 до 8567 ?

A>>Заведём массив A размера N. Пройдёмся по всем элементам массива векторов и будем в ячейку с номером равным элементу слева записывать значение равное элементу справа.
F_G>А если координаты вершин — не натуральные числа ?

Всё просто. Нужно только создать словарик, и тогда массив нужен только размером N. Кстати, составление словарика — операция трудоёмкостью O(N).
Пример для одномерных векторов:

12.3  23.4
8451  6824
0.11  12.3
6824  0.11
23.4  8451

За первый проход составляем словарик:

n | v
--------
1 | 12.3
2 | 23.4
3 | 8451
4 | 6824
5 | 0.11

и дальше вместо v оперируем n.
Метода легко распространяется на многомерный случай. Пример словарика:

n | v
-------------------------------------
1 | (65456, 84524, 87878.33333333333)