Zeit Komplexität der folgenden Wiederholung?

Question

Finden Sie heraus, die Zeit Komplexität (Big Oh Bound) der Wiederholung T(n) = T(⌊n⌋) + T(⌈n⌉) + 1.

Wie die Zeit Komplexität von diesem kommt heraus O(n) ??

Answer 1

Sie wahrscheinlich T(n)=T(⌊n/2⌋)+ T(⌈n/2⌉) + 1.

Lässt sich die ersten paar Werte von T(n) berechnen.

T(1) = 1 
T(2) = 3 
T(3) = 5 
T(4) = 7 

können wir das T(n) = 2 * n - 1 erraten.

Ermöglicht das beweisen durch mathematical induction

Basis

T(1) = 1 
T(2) = 3 
T(3) = 5 
T(4) = 7 

Induktive Schritt

T(2*n) = T(⌊2*n/2⌋)+ T(⌈2*n/2⌉) + 1 
    = T(⌊n⌋)+ T(⌈n⌉) + 1 
    = (2*n - 1) + (2*n - 1) + 1 
    = 4*n - 1 
    = 2 * (2*n) - 1 

T(2*n+1) = T(⌊(2*n+1)/2⌋)+ T(⌈(2*n+1)/2⌉) + 1 
    = T(n)+ T(n+1) + 1 
    = (2*n - 1) + (2*(n+1) - 1) + 1 = 
    = 4*n + 1 = 
    = (2*n+1)*2 - 1 

Da sowohl die Basis und der induktive Schritt erwiesen haben, wurde nun durch mathematische Induktion nachgewiesen worden dass T (n) für alle natürlichen 2 * n - 1 gilt.

T(n) = 2*n - 1 = O(n)

Answer 2

Was Sie gerade haben, macht keinen Sinn. Da n normalerweise eine natürliche Zahl ist, dann n=⌊n⌋=⌈n⌉. Die Wiederholung lautet dann: Brechen Sie ein Problem der Größe n in zwei Probleme der Größe n und verbringen Sie Zeit 1 dabei. Die zwei neuen Probleme, die Sie gerade erstellt haben, werden nacheinander aufgeteilt, und alles, was Sie tun, ist, mehr Arbeit für sich selbst zu schaffen.