Алгоритми та структури даних · Middle · Запитання 52 з 75
Яка просторова складність рекурсивного DFS на дереві висотою h?
- 1O(n²) на множину visited
- ✓Правильна відповідь: O(h) на стек викликів
- 3O(1), бо нічого не зберігається
Пояснення
У будь-який момент стек містить по фрейму на кожен рівень поточного шляху. Для збалансованого дерева h дорівнює log n, для виродженого - n.