Моят основен случай грешен ли е? - Рекурентна връзка за алгоритъм с множество повторения

Трябва да създам връзка на повтаряне, за да уловя броя на сравненията, извършени в този алгоритъм:

Func(n)
    if n = 1
        print "!"
        return 1
    else
        return Func(n-1) * Func(n-1) * Func(n-1)

Това е, което измислих - но изглежда не мога да разбера какво съм направил грешно...

Основен случай: M(1) = 0

M(n) = 3[M(n-1)] 
 = 3[3[M(n-2)]]
 = 3[3[3[M(n-3)]]]
 = 3^i[M(n-i)]

i = n-1 //to get base case

M(n) = 3^(n-1)[M(n-(n-1))] 
 = 3^(n-1)[M(1)] 
 = 3^(n-1)[0] 
 = 0 //????????????

Моят основен случай грешен ли е? Ако да защо? Моля и ви благодаря за помощта.


recurrence relation algorithm
person Shannon    schedule 25.10.2014    source източник
comment
Какво ви накара да мислите, че M(1) = 0?   -  person wookie919    schedule 25.10.2014
comment
@wookie919 Честно казано, нямам представа. Винаги се бъркам с основните случаи.   -  person Shannon    schedule 25.10.2014

Отговори (2)


arrow_upward
2
arrow_downward

За основен случай (n е равно на 1), M(1) трябва да се приеме като 1 (константа на времева сложност),

M(n) = 3^(n-1) then
person Dr. Debasish Jana    schedule 25.10.2014

arrow_upward
0
arrow_downward

Въпросът е за броя на сравненията.

Всеки път, когато извикате функцията, изпълнявате точно едно сравнение.

Когато резултатът е n=1, сте готови, а когато резултатът е n>1, извършвате три рекурсивни извиквания с n-1.

ясно,

M(1) = 1 
M(n) = 3 M(n-1)

Като изчислявате M за нарастващи стойности на n, вие лесно забелязвате модела: 1, 3, 9, 27, 81...

person Yves Daoust    schedule 25.10.2014
comment
Има нещо забавно в тази функция, когато погледнете какво изчислява: F(n) = F(n-1)^3 = F(n-2)^9 = F(n-3)^27 = .. .. F(n-k)^(3^k) = ... F(1)^(3^(n-1)) = 1. Винаги връща 1, след вероятно много дълго време. - person Yves Daoust; 25.10.2014