Изменения
Нет описания правки
<tex>sort(X)</tex> // сортируем элементы по возрастанию веса
<tex>B \leftarrow \emptyset</tex>
'''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>\mid |X \mid|-1</tex> '''do'''
'''if''' <tex>B \cup X[i] \in I</tex>
<tex>B \leftarrow B \cup X[i]</tex>
Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По [[Теорема Радо-Эдмондса (жадный алгоритм)|теореме Радо-Эдмондса]] множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из <tex>X</tex> так, чтобы после каждого добавления множество оставалось независимым.
Алгоритм работает за <tex>O(\mid |X | \mid log(\mid |X \mid|))</tex>. На сортировку элементов из <tex>X</tex> по возрастанию весов уходит <tex>O(\mid |X | \mid log(\mid |X \mid|))</tex> и <tex>O(\mid X \mid)</tex> шагов цикла, каждый из которых работает <tex>O(1)</tex> времени (если считать, что проверка множества на независимость происходит за <tex>O(1)</tex>).
}}
