анализ сложности рекурсивного алгоритма с неравномерным делением

меня попросили проанализировать временную сложность следующего рекурсивного уравнения с использованием итеративного метода:анализ сложности рекурсивного алгоритма с неравномерным делением

Т (п) = Т (п/3) + T (2n/3) + п^2.

T (1) = 1

когда я пытаюсь расширить уравнение, взрывает, и я не могу следить за всеми рекурсивный «называет» и константы. Это вызвано неравномерным разделением данных (1 \ 3 - 2 \ 3).

Есть ли более простой способ решить эту проблему с помощью итерационного метода?

Большое спасибо.

источник

2013-03-20 Paz

Вы можете использовать метод Akra-Bazzi, чтобы найти решение в первую очередь. –

Вы пытались найти это точное уравнение? – jamylak

Что такое 'T (0)'? 0? – Claudiu

Вроде бы O (N^2), если я не пропустил ничего ...

Прежде всего Т монотонно растет (в течение нескольких первых значений, которые вы можете проверить это вручную, для остальных это по индукция - если функция монотонна в [1..10], то она будет монотонна на [1..15] и т. д.).

T(n)=T(n/3)+T(2n/3)+n^2<=2T(2n/3)+n^2 
T(n)<=n^2+2*(2n/3)^2+4*(4n/9)^2+... 
    =sum[k=0..log3(n)]((8/9)^k*n^2) 
    =n^2*sum[k=0..log3(n)](8/9)^k 
    <=n^2*sum[k=0..inf](8/9)^k 
    <=C*n^2

источник

2013-03-20 14:13:28 maxim1000

Я немного новичок в этом, но можем ли мы всегда считать, что большая часть занимает больше времени, чем меньшая? (Я вижу вас с верхней границей исходной последовательности с 2T (2n/3)) – Paz

@ user2190298: Я добавил объяснение о монотонности, ясно ли это? – maxim1000

Да. кристалл. благодаря! – Paz

Here является бумага, которая показывает анализ похож формулы: Т (п) = Т (п/3) + T (2n/3) + п

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

Применение формулы: T (n) = T (n/3) + T (2n/3) + n^2 с n = 1..9 дает

T(0) = 0 

T(1) = T(1/3) + T(2/3) + 1 

T(2) = T(2/3) + T(4/3) + 4 

T(3) = T(1) + T(2) + 9 

T(4) = T(4/3) + T(8/3) + 16 

T(5) = T(5/3) + T(10/3) + 25 

T(6) = T(2) + T(4) + 36 

T(7) = T(7/3) + T(14/3) + 49 

T(8) = T(8/3) + T(16/3) + 64 

T(9) = T(3) + T(6) + 91 

T(3m) = T(m) + T(2m) + 9m^2

.. Возможно, это может дать вам несколько советов

источник

2013-03-20 14:46:46

Что здесь помогает, чтобы не размножаться ни с одним из чисел, а писать все в терминах полномочий. Делать это все вручную, я получил следующее за первые несколько расширений:

T(n) = T((1/3)n) + T((2/3)n) + n^2 
    = T((1/3^2)n) 
     + 2T((2/3^2)n) 
     + T((2^2/3^2)n) 
     + [n^2]      #constants from the first expansion 
     + [((1/3)n)^2 + ((2/3)n)^2] #constants from the second expansion 
    = T((1/3^3)n) 
     + 3T((2/3^3)n) 
     + 3T((2^2/3^3)n) 
     + T((2^3/3^3)n) 
     + [n^2] 
     + [((1/3)n)^2 + ((2/3)n)^2] 
     + [((1/3^2)n)^2 + ((2/3^2)n)^2 + ((2^2/3^2)n)^2] #constants from 3rd expansion

Это немного трудно сказать, но то, что, кажется, происходит то, что вы получаете биномиальных коэффициентов, идущие для T с, где x го расширения выглядит следующим образом:

T(n) = sum((x choose i) * T(((2^i)/(3^x))n), i from 0 to x) 
     + constants

на каждом шаге, дополнительные константы, которые добавляются при расширении x являются аргументами T от расширения x-1, квадрат, так как все они в конечном итоге получить в квадрат благодаря n^2.Таким образом, все новая константа в данном разложении y равна:

NewConsts(y) = sum(((y - 1) choose i) * (((2^i)/(3^(y-1)))*n)^2, i from 0 to y - 1)

И всех константы при расширении x равна

n^2 + sum(NewConsts(y), y from 1 to x)

Итак, предполагая, что все вышесказанное является правильным , на что я не уверен на 100%, я думаю, вам нужно выяснить, когда константы перестают иметь значение, то есть для x равно ((2^x/3^x) * n)^2), равным 0, и ваш ответ - сумма всех этих констант .. .

источник

2013-03-20 15:14:56 Claudiu

анализ сложности рекурсивного алгоритма с неравномерным делением

ответ

Смежные вопросы