Big O — асимптотическая верхняя оценка роста ресурса (времени или памяти) по мере роста размера входа. Формально выражает, как меняется количество операций или дополнительной памяти при $n\to \infty$; константы и низкоуровневые детали игнорируются.
Временная сложность — сколько простейших операций (например, проверок/просмотров рёбер/вершин) выполняет алгоритм в зависимости от размера входа.
Пространственная сложность — сколько дополнительной памяти (не считая памяти, требуемой для хранения входных данных) нужно алгоритму.
Применение к DFS и BFS (граф представлен списками смежности, число вершин $|V|$, число рёбер $|E|$):
- Время:
- DFS (рекурсивный или стековый): посещает каждую вершину и каждое ребро не более одного раза, поэтому временная сложность $O(|V|+|E|)$.
- BFS: аналогично посещает каждую вершину и ребро максимум один раз, временная сложность $O(|V|+|E|)$.
- При представлении графа матрицей смежности обеим алгоритмам время будет $O(|V{|}^2)$, т.к. приходится сканировать строки матрицы.
- Память (дополнительная):
- DFS:
- Рекурсивная реализация: стек вызовов глубиной в худшем случае $|V|$, т.е. $O(|V|)$.
- Итеративная (явный стек): аналогично $O(|V|)$.
- В частных случаях на сбалансированном дереве глубина меньше: для дерева с $n$ вершинами и высотой $h$ — стек $O(h)$; для сбалансированного бинарного дерева $h=O(\log n)$.
- BFS:
- Использует очередь для фронта обхода; в худшем случае может одновременно содержать $\Theta (|V|)$ вершин, т.е. пространство $O(|V|)$.
- В частном примере полного бинарного дерева с $n$ вершинами максимальный уровень содержит $\Theta (n)$ вершин → очередь $O(n)$.
Короткое сравнение/вывод:
- По времени для стандартных представлений оба алгоритма одинаковы: $O(|V|+|E|)$ (или $O(|V{|}^2)$ для матрицы).
- По памяти различия зависят от структуры графа: в худшем случае оба требуют $O(|V|)$, но на «глубоких» и сбалансированных деревьях DFS может требовать лишь $O(\log n)$ (рекурсивная глубина), тогда как BFS может требовать $O(n)$ для хранения уровня.