34
правки
Изменения
Нет описания правки
Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По [[Теорема Радо-Эдмондса (жадный алгоритм)|теореме Радо-Эдмондса]] множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из <tex>X</tex> так, чтобы после каждого добавления множество оставалось независимым.
Алгоритм работает за <tex>O(n \log n + mn)</tex>. На сортировку элементов из <tex>X</tex> по возрастанию весов уходит <tex>O(n \log n)</tex> и . После чего, построение базы выполняется <tex>O(n)</tex> шагов цикла, каждый из которых работает <tex>O(m)</tex> времени. Однако, если считать, что проверка множества на независимость происходит за <tex>O(1)</tex>, асимптотика алгоритма будет <tex>O(n \log n)</tex>
}}
