Algorytmy i struktury danych · Middle · Pytanie 52 z 75
Jaka jest złożoność pamięciowa rekurencyjnego DFS na drzewie o wysokości h?
- 1O(n²) na zbiór visited
- ✓Poprawna odpowiedź: O(h) na stos wywołań
- 3O(1), bo nic nie jest przechowywane
Wyjaśnienie
W każdej chwili stos zawiera po jednej ramce na poziom bieżącej ścieżki. Dla zbalansowanego drzewa h to log n, dla zdegenerowanego n.