Базовый случай основной теоремы постоянен?

Предполагает ли основная теорема, что T(1) постоянна? Скажем, если у меня есть алгоритм с временной сложностью: T(n) = 2T(n/2) + O(1) и T(1) = O(logn), какова временная сложность этого алгоритма?


algorithm master-theorem
person ZigZagZebra    schedule 30.01.2016    source источник
comment
T(1) = O(logn) бессмысленно: размер задачи не может быть параметризованным и постоянным. Это опечатка?   -  person Michael Foukarakis    schedule 31.01.2016
comment
Проблема, которую я пытаюсь решить, заключается в том, что у меня есть n точек и m меток. Каждой точке присваивается метка. m может быть меньше n. Я хочу разделять и властвовать по меткам, а не по очкам. Таким образом, моя рекурсия становится T (m) = 2T (m/2) + O (1), а временная сложность решения точек с одной и той же меткой составляет O (logn). Есть ли способ решить эту проблему? Или я ошибаюсь в своем уравнении.   -  person ZigZagZebra    schedule 31.01.2016
comment
Действительно, существуют способы решения многомерных рекуррентных соотношений. Посмотрите похожие вопросы по математике здесь и здесь.   -  person Michael Foukarakis    schedule 31.01.2016

Ответы (3)


arrow_upward
0
arrow_downward

Для рекуррентного соотношения: T(n) = 2T(n/2) + O(1) имеем

  • a = 2
  • b = 2
  • работа за O(1) времени вне рекурсии

поэтому применим случай основной теоремы 1, и мы имеем:

T(n) ∈ Θ(n ^ log2(2)) ⇒

T(n) ∈ Θ(n)

Рекуррентное отношение определяет последовательность на основе начального термина. Если задача размера 1 решается рекуррентным соотношением T(1) = f(n), где f ∈ O(logn), значение T(1) не может быть определено, т. е. не имеет смысла как рекуррентное соотношение.

person Michael Foukarakis    schedule 30.01.2016
comment
Вы видите мой комментарий выше? Я добавил больше деталей к проблеме. - person ZigZagZebra; 31.01.2016

arrow_upward
0
arrow_downward

Ваше утверждение T(1) = O(logn) не имеет никакого смысла. Вы в основном утверждаете, что некоторая функция, которая по какой-то причине не зависит от n, имеет логарифмическую сложность (таким образом, зависит от n логарифмическим способом).

T(1), T(2), T(532143243) являются граничными условиями и не могут зависеть ни от одного параметра. Они должны быть числом (5, pi/e, sqrt(5) - i)

person Salvador Dali    schedule 30.01.2016

arrow_upward
0
arrow_downward

Иногда лучше просто попробовать, чем полагаться на теорему.

T(m) = 2T(m/2) + O(1)
T(1) = O(logn)

T(2) = 2T(1) = 2log(n)
T(4) = 2T(2) = 4log(n)
T(8) = 2T(4) = 8log(n)
T(16) = 2T(8) = 16log(n)
T(32) = 2T(16) = 32log(n)
T(m) = 2T(m/2) = mlog(n)

В заключение, ваш первоначальный вопрос действительно бессмыслен, как указывали другие, потому что вы пытаетесь вычислить T(n), когда один и тот же n используется в T(1) = O(logn). Но мы можем ответить на ваш второй вопрос, который вы добавили в качестве комментария.

person wookie919    schedule 27.06.2016