О-нотация это классический способ оценки временной сложности выполнения алгоритмов. В сущности это показатель времени выполнения алгоритма в самом худшем и неоптимальном случае его использования.
Дерево решений
Какова будет сложность построения дерева в нотации О большое, если размер выборки равен N, а количество признаков равно M?
Оценка временной сложности построения дерева решений (например, DecisionTreeClassifier из scikit-learn) в терминах O-большое зависит от нескольких факторов.
Обозначения:
- N — количество объектов (строк) в выборке
- M — количество признаков
- D — максимальная глубина дерева
Временная сложность построения одного дерева:
В наихудшем случае — когда дерево полностью разветвляется до листьев (до уровня, где каждый объект оказывается в отдельном узле):
O(M⋅NlogN)
Пояснение по шагам:
- На каждом узле:
- Нужно выбрать наилучший признак и порог разбиения.
- Для одного признака — это O(NlogN), если значения признака сортируются.
- Для M признаков — O(M⋅NlogN).
- Сколько таких узлов будет?
- При сбалансированном дереве глубиной D, количество узлов — O(2^D), но суммарное количество проверок по всем уровням оценивается в O(N), потому что каждый объект проходит по одному пути от корня до листа.
Итого:
O(M⋅NlogN)