Отбрасывать менее значимые термины в середине расчета сложности времени?

Question

Мы знаем, что для некоторого алгоритма с временной сложностью, скажем, T(n) = n^2 + n + 1 мы можем отбросить менее значимые термины и сказать, что у него наихудший случай O(n^2).

Как насчет того, когда мы в середине расчета сложности времени алгоритм, такой как T(n) = 2T(n/2) + n + log(n)? Можем ли мы просто отбросить менее значимые термины и просто сказать T(n) = 2T(n/2) + n = O(n log(n))?

Answer 1

В этом случае, да, вы можете безопасно отказаться от доминирующего (log n) термина. В общем, вы можете сделать это в любое время, когда вам нужно только асимптотическое поведение c, а не точная формула.

Когда вы применяете основную теорему для решения рекуррентного отношения, например

T (n) = a T (n / b) + f (n)

асимптотически, тогда вам не нужна точная формула для f (n), только асимптотическое поведение c, потому что так работает теорема Мастера.

В вашем примере a = 2, b = 2, поэтому критический показатель равен c = 1. Тогда теорема Мастера говорит нам, что T (n) находится в Θ (n log n), потому что f (n) = n + log n, что в Θ (n ^c) = Θ (n).

Мы бы пришли к такому же выводу, используя f (n) = n, потому что это также в Θ (n). Применение теоремы требует только знания асимптотического c поведения f (n), поэтому в этом контексте безопасно отбрасывать доминирующие термины, которые не влияют на асимптотическое поведение f (n) c .

Answer 2

Прежде всего вам необходимо понять, что T(n) = n^2 + n + 1 является выражением закрытой формы, в простых терминах это означает, что вы можете ввести некоторое значение для n, и вы получите значение всего этого выражения.

on С другой стороны, T(n) = 2T(n/2) + n + log(n) является рекуррентным отношением , это означает, что это выражение определено рекурсивно, чтобы получить выражение закрытой формы, вам придется решить рекуррентное отношение.

Теперь, чтобы ответить на ваш вопрос, как правило, мы опускаем члены и коэффициенты низшего порядка, когда мы можем ясно видеть член высшего порядка, в T(n) = n^2 + n + 1 его n ^ 2. но в рекуррентном отношении нет такого члена высшего порядка, потому что это не выражение закрытой формы.

, но следует заметить, что член высшего порядка в выражении замкнутой формы отношения рекуррентности будет результат дерева глубины повторения, умноженный на член высшего порядка в отношении повторения , так что в вашем случае это будет depthOf(2T(n/2)) * n, это приведет к чему-то вроде logn*n, так что вы можете скажем, что с точки зрения обозначения большой O его O(nlogn).