0 / 0 / 0
Регистрация: 26.04.2016
Сообщений: 3
|
||||||
1 | ||||||
Задача по сортировке26.04.2016, 10:24. Показов 2690. Ответов 6
Метки нет (Все метки)
Здравствуйте форумчане, перепала такая задача: Существует некоторый перечень карточек. Каждая карточка содержит в себе пункт отправления и пункт назначения. Гарантируется что если упорядочить эти карточки так чтобы для каждой карточки в упорядоченном списке пункт назначения на ней совпадал с пунктом отправления в следующей карточке в списке, получится один список карточек без циклов и пропусков. Необходимо написать функцию которая принимает набор неупорядоченных карточек и возвращает набор упорядоченных.
Накидал алгоритм, прошу ткнуть носом что и где криво, буду благодарен за ссылки, статьи, книги, названия алгоритмов итд.
0
|
26.04.2016, 10:24 | |
Ответы с готовыми решениями:
6
Задача по сортировке массивов Задача по быстрой сортировке Задача по сортировке учащихся Задача по сортировке двумерного массива |
1494 / 1209 / 821
Регистрация: 29.02.2016
Сообщений: 3,614
|
|
26.04.2016, 17:39 | 2 |
Задача о коммивояжере
Метод ветвей и границ: Нахождение минимального пути между городами
0
|
17685 / 12871 / 3365
Регистрация: 17.09.2011
Сообщений: 21,136
|
|
26.04.2016, 18:50 | 3 |
0
|
1494 / 1209 / 821
Регистрация: 29.02.2016
Сообщений: 3,614
|
|
26.04.2016, 19:10 | 4 |
Ну тогда здесь можно найти рабочий пример
http://www.codeproject.com/Art... -Algorithm
1
|
0 / 0 / 0
Регистрация: 26.04.2016
Сообщений: 3
|
|
27.04.2016, 09:29 [ТС] | 5 |
интересное решение, но все же это не то. В моей задаче необходимно написать функцию сортировки которая отработает за конечное время, определить сложность алгоритма итд. В приведенной статье рассматривается алгоритм поиска оптимального пути, что по сути является вариацией решения задачи о коммивояжере с использованием генетического алгоритма.
0
|
27.04.2016, 10:49 | 6 |
Сообщение было отмечено cz как решение
Решение
Сложность у вас O(n^2).
1) Вместо List<Card> list нужно использовать коллекцию другого типа, у которой удаление элемента проходит за O(1), например LinkedList или HashSet. У List<Card> удаление проходит за O(n), что существенно замедляет ваш алгоритм. 2) А вот вместо Queue<Card> sorted как раз нужно использовать List<Card>. Это не влияет на быстродействие, а просто семантически более верно, потому что вам очередь не нужна, вы просто формируете выходной список. А очередь нужна только тогда, когда вам нужно извлекать элементы из головы списка, но у вас этого нет. 3) Игр с интернацией строк я не очень понял. Вероятно вы так пытаетесь повысить быстродействие? Ну во-первых в вашем случае строки всегда и так будут интернированы, потому что они у вас вообще константы. Во-вторых, это как раз тот случай, когда преждевременная оптимизация вредна. На O() это не влияет, зато усложняет код. Ну и в целом. Ваш алгоритм работает за O(n^2). Вы пробегаетесь по всему списку карточек (это O(n)) и затем для каджой ищите в списке следующую карточку (умножаем еще на O(n)). Но можно же сделать и за O(n). Для этого сформируйте словарь вида Dictionary<string, Card>, который будет хранить карточки по начальному пункту (ключ в словаре). Тогда пробегаясь в цикле по карточкам, вы сразу найдете следующую карточку по словарю за O(1). Формирование словаря занимает O(n), ваш цикл while займет O(n)*O(1). Т.о. общее быстродействие будет O(n) + O(n)*O(1) = O(n).
1
|
0 / 0 / 0
Регистрация: 26.04.2016
Сообщений: 3
|
|
27.04.2016, 11:26 [ТС] | 7 |
Добавлено через 9 минут огромное спасибо за коментарии. не могли бы вы порекомендовать ресурс где можно почитать об оптимизации ? ну кроме МСДН) Интренирование конечно в данном конкретном примере абсолютно бессмысленно. еще раз спасибо
0
|
27.04.2016, 11:26 | |
27.04.2016, 11:26 | |
Помогаю со студенческими работами здесь
7
Задача по сортировке двумерного массива, найти ошибку Задача по сортировке диагоналей массивов методом вставок Ошибка в сортировке Ошибки в сортировке Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |