Я начинаю изучать сложность времени, и я смотрел в примерах временную сложность для некоторого простого вида.
Я хотел знать, как мы вычисляем среднюю временную сложность для поиска по глубине в графе с |V|=n и |E|=m, пусть начало node be 'u' и end node be 'v.
Сложность времени для DFS равна O (n + m). Мы получаем эту сложность, учитывая тот факт, что мы посещаем каждый node только один раз, а в случае дерева (без циклов) мы пересекаем все края один раз.
Например, если начало node равно u, а конец node равен v, мы думаем в худшем случае, когда v будет последним посещенным node. Итак, мы начинаем посещать каждого первого соседа u подключенного компонента, затем подключенного компонента второго соседа и т.д. До последнего компонента, подключенного к последнему, где мы находим v. Мы посетили каждый node только один раз и didn ' t пересек один и тот же край более одного раза.
это будет O (n + m), если граф задан в виде списка смежности, но если граф находится в виде матрицы смежности, то сложность равна O (n * n), так как мы должны пройти через всю строку, пока не найдем ребро.