Тема: Алгоритм Крускала
Вопрос по асимптотике в статье. Почему сортировка ребер работает за O(MlogN) , ведь вроде бы логарифм тоже от числа ребер?
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Алгоритм Крускала
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Вопрос по асимптотике в статье. Почему сортировка ребер работает за O(MlogN) , ведь вроде бы логарифм тоже от числа ребер?
Наверное, потому что O(log M) = O(log N^2) = O(log N)
Точно) Спасибо)
Хотя это, наверное, странная уловка - ведь с точки зрения скрытой константы более информативно написать "log M"
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Алгоритм Крускала