Как итеративное углубление влияет на временную сложность?

У меня есть алгоритм обхода дерева, который обычно работает за O(bm), где b — коэффициент ветвления, а m — максимальная глубина.

Используя итеративное углубление, этот алгоритм запускается снова и снова, m раз с увеличением глубины:

O(bm) = b⁰ + b¹ + b² + ... + bm

Основываясь на моем ограниченном понимании временной сложности, мы берем самый большой элемент, потому что он является наиболее значимым во времени, и поэтому этот элемент будет bm, где m — максимальная достигнутая глубина.

Итак, зная это, я бы сделал вывод, что алгоритм итеративного углубления также работает за O(bm).

Однако мне трудно понять с логической точки зрения, как обход дерева может иметь одинаковую временную сложность, независимо от того, выполняется ли алгоритм один раз на глубине m или m раз до глубины m.

bm по своей сути меньше, чем Σk=0,..,mbk. Следовательно, не должна ли временная сложность при итеративном углублении быть выше?

Или я чего-то не понимаю?


algorithm big-o depth-first-search tree-traversal iterative-deepening
person SemperCallide    schedule 08.12.2013    source источник

Ответы (2)


arrow_upward
3
arrow_downward

В основном вы спрашиваете, почему следующие две функции имеют одинаковую временную сложность с точки зрения большого O (поскольку они оба O (n ^ m)):

  • n^0 + n^1 + n^2 + ... + n^m
  • n^m

Причина в том, что в какой-то момент для значений n и m член n^m затмевает все остальные члены этих функций. По мере роста входных данных время выполнения функции в целом будет определяться n^m.

Даже если вы придумаете функцию, которая принимает n^m + 1000000000000, то в какой-то момент n^m все равно будет решающим фактором в том, сколько времени потребуется для выполнения. Другими словами, время выполнения обеих функций ограничено функцией с членом n^m, умноженным на некоторую константу.

В вашем примере запуск обхода дерева один раз на глубине m или запуск его m раз до тех пор, пока глубина m не будет иметь одинаковую временную сложность, потому что по мере роста дерева время выполнения на глубине m затмевает все остальные прогоны. Глядя на то, сколько времени требуется для выполнения на глубине m, в основном все, что нужно, чтобы найти функцию, которая ограничивает время выполнения обеих задач.

Чтобы привести еще один пример, мы можем думать о двух функциях, которые обе являются O (n):

  • f1(n) = 1000000000n + 5
  • f2(n) = 3n

Может показаться, что f1 выполняет больше работы по мере роста n, поэтому несправедливо говорить, что оба значения равны O(n). Но их временная сложность ограничена линейной функцией: для некоторой (большой) константы c я могу сказать, что время выполнения обеих функций будет ниже f(n) = cn, и, таким образом, временная сложность в целом составляет O(n).

person Simeon Visser    schedule 08.12.2013

arrow_upward
2
arrow_downward

«Точная же» временная сложность — это не то же самое, что «точное время». Сказать «Сложность с одинаковым временем» все равно что сказать «растет с той же скоростью, до постоянного коэффициента», что является грубой оценкой.

Например, если b = 3, вы сравниваете эти две последовательности чисел:

3^m,             or (1, 3,  9, 27,  81, ...)
3^0+3^1+...+3^m, or (1, 4, 13, 40, 121, ...)

Обозначим первое число D(m) (для "DFS"), а второе I(m) (для "итеративного углубления"), тогда

I(m) = 3/2 * D(m) - 1/2

Конечно, I(m) больше, чем D(m), но они имеют один и тот же «порядок» роста. Эта идея обозначена I(m) = O(D(m)).

Математически I(m) = O(D(m)), потому что существует такая константа k, что I(m) < k * D(m) для всех m; здесь k = 3/2.

person anatolyg    schedule 08.12.2013