已知非齊次遞歸方程:其中,b、c是常數(shù),g(n)是n的某一個函數(shù)。則f(n)的非遞歸表達(dá)式為:現(xiàn)有Hanoi塔問題的遞歸方程為:,求h(n)的非遞歸表達(dá)式。
利用給出的關(guān)系式,此時有:b=2,c=1,g(n)=1,從n遞推到1,有:
O(n*2n);O(min{nc,2n})