лучший вариант для сортировки ребер в алгоритме Крускала?

Я реализую алгоритм Крускала, и я не уверен, как лучше упорядочить ребра. Мне нужна лучшая временная сложность для больших входных данных (300 000+ ребер). Я знаю, что они похожи по временной сложности, но я хотел бы знать, что быстрее для больших входных данных.


time-complexity heap quicksort kruskals-algorithm
person mereth    schedule 07.04.2017    source источник
comment
Начните с использования функции сортировки, предоставляемой библиотекой. Заставьте ваше решение работать. Это вполне может быть достаточно быстро. Если это не так, то профилируйте и решите, является ли это сортировкой или чем-то еще, что вызывает замедление. Обратите внимание, однако, что если вы действительно не умеете оптимизировать код, ваша пользовательская сортировка, скорее всего, будет медленнее, чем встроенная версия.   -  person Jim Mischel    schedule 11.04.2017
comment
Я использовал библиотеку qsort() в c, и этого было достаточно. Спасибо за ваш комментарий.   -  person mereth    schedule 11.04.2017

Ответы (1)


arrow_upward
1
arrow_downward

Начните с использования функции сортировки, предоставляемой библиотекой. Заставьте ваше решение работать. Это вполне может быть достаточно быстро. Если это не так, то профилируйте и решите, является ли это сортировкой или чем-то еще, что вызывает замедление. Обратите внимание, однако, что если вы действительно не умеете оптимизировать код, ваша пользовательская сортировка, скорее всего, будет медленнее, чем встроенная версия.

person Jim Mischel    schedule 11.04.2017