recidiva solving [chiuso]

Question

Ho bisogno di trovare la complessità della ricorrenza corrente:

T(n) = 1/(T(n-1) + 1) + 1

Grazie in anticipo per qualsiasi idea o legame con informazioni utili

Answer 1

Ampliando i miei commenti sopra ...

Questo non ha senso come un rapporto recidiva del mondo reale. T(n) denota il runtime per risolvere un problema di dimensione n; T(n-1) indica la runtime per dimensioni (n-1). Dato che è necessario risolvere il problema per le dimensioni (n-1) prima di poter risolvere per n dimensioni (altrimenti non sarebbe una ricorsione), il runtime deve essere necessariamente monotona all'aumentare n.

Tuttavia, la tua espressione oscilla su e giù con n; questo non ha senso.

L'unico modo questa espressione potrebbe mai senso è se si assume che T(n) è costante n, in modo che non vi sia oscillazione. Si scopre che esiste un valore costante che permette che questo accada, solo set T(n) = T(n-1), e risolvere. (Si noti che questo è altrettanto priva di senso;. Non generalmente parliamo di assoluto valori di T(n))