pro.algorithms
Подскажите, пожалуйста, в чем может быть проблема в странных результатах
сравнения BFS по графу представленному матрицей смежности и спискам смежности?
Задача в том чтобы сравнить на практике эти два способа
Исходил из того что сложность обхода по матрице n^2, а по спискам n+e, ожидал что замеры обеда по матрице будут улетать в космос
Но как я не замерял, при разных сочетаниях количества вершин и граней (граф генерится рандомно) - результаты в пользу матрицы или же они примерно одинаковые
С чем это может быть связано?
Перерыл код реалиации на списках смежности, намека на квадратичную сложность не нашел
2 ответов
какое максимальное количество вершин в ваших тестах?
А попробуй по-честному замерить сложность? Заведи глобальный счётчик и инкрементируй каждый раз при какой-то существенной операции (доступ к одному узлу или дуге, например). Потому что на самом деле при замерах времени из-за кучи дополнительных возмущений можно разную сложность не отличить на определённых диапазонах количества вершин и дуг.
Похожие вопросы
Обсуждают сегодня