Тема: Алгоритм Крускала

Вопрос по асимптотике в статье. Почему сортировка ребер работает за O(MlogN) , ведь вроде бы логарифм тоже от числа ребер?

2

Re: Алгоритм Крускала

Наверное, потому что O(log M) = O(log N^2) = O(log N)

test

3

Re: Алгоритм Крускала

Точно) Спасибо)

4

Re: Алгоритм Крускала

Хотя это, наверное, странная уловка - ведь с точки зрения скрытой константы более информативно написать "log M" smile