der Suche nach Komplexität Induktion

Question

ich gebeten wurde, zu beweisen:

für jedes n> = n0 und T(n) = T(an) + T(bn) + n für n> n0, a + b < 1, ist seine Komplexität T(n) = O(n).

Hinweis: Beweisen Sie durch Induktion, dass: T(n) ≤ cn für eine geeignete c.

Ich wollte in diesem Fall wie durch Induktion beweisen.

Vielen Dank.

Answer 1

Wenn wir postulieren die Ungleichheit wahr zu sein für an und bn, dann

Wir wissen aber nicht, die genaue Beziehung zwischen dieser Konstante und c; aber wenn wir uns den Fall, dass

Aber a + b kann auf 1 beliebig nahe sein, was bedeutet, dass c wäre beliebig groß. Diese Art vereitelt den Punkt der O-Notation, da die Konstante endlich sein muss. Deshalb nehmen wir die untere Grenze:

Daher haben wir den Bereich von c für die fand das Postulat wahr sein kann. Die untere Grenze von 1 ist, weil Ihre Domäne n >= n0 bedeutet, dass T(n0) = n0. Hier ist die Konstante 1, also muss c mindestens 1 sein, um die postulierte Anfangsgrenze zu erfüllen. Dies schränkt auch die Werte a und b positiv ein.

Aber für das Postulat wahr zu sein, a, bjeden Wert in [0, 1) nehmen kann, was bedeutet, dass, wenn die Schranke für T(n) korrekt ist dann beispielsweise für jeden größeren Parameter auch richtig ist T(n + 1).

So wissen wir, dass:

1. Die Hypothese für n = n0
2. Wenn true für n dann gilt auch für n + 1

daher durch Induktion, T(n) <= cn für jede n >= n0 wahr ist, wo c erfüllt die Grenzen von früher.