Wie mathematisch ableiten Höhe und Anzahl der Blätter dieser Rekursionsbaum

ich folgende Baum studierte und auf Ableitung Höhe & Anzahl der Blätter stecken: Wie mathematisch ableiten Höhe und Anzahl der Blätter dieser Rekursionsbaum

Er sagt, [die Höhe ist log _b n]: Wie kann man es ableiten? (auch ich denke, height = [log _b n] + 1)

Wie Sie leiten Anzahl der Blätter: ein ^{log _b n} = n ^{log _b ein}

Bitte helfen Sie mir mathematisch Höhe & Anzahl der Blätter dieses Rekursionsbaum auf eine sehr einfache Art abzuleiten.Dank

Quelle

2016-07-10 user5005768

Höhe
Die Spitze des Baumes beginnt mit n und für jeden Schritt nach unten ist es durch b unterteilt. So geht es n, n/b, , ..., 1. Um die Höhe wir einen k so finden müssen, dass n/b ^k = 1 oder b ^k = n, die k gibt = log _b n.

Anzahl der Blätter
Für jeden Schritt auf dem Baum werden die Blätter von ein mal multipliziert. Die Anzahl der Blätter ist a ^k, wobei k die Anzahl der Stufen oder die Höhe des Baumes ist. Die Anzahl der Blätter = a ^{log _b n}.

Quelle

2016-07-10 06:19:15

Dank @ Sneha.Very Schöne & Einfache Erklärung.Allerdings habe ich ein Beispiel verwendet, um die Baumhöhe zu testen. Wenn z. B. b = 2 und n = 8 ist, dehnt sich der Baum von 8,4,2,1 bis zu 4 Stufen aus, aber log b^n = log2^8 = 3 Nicht 4? Können Sie bitte mehr erklären. Danke – user5005768

Höhe des Baumes wird normalerweise als die Anzahl der Schritte von der Wurzel des Baumes gemessen. In diesem Fall ist 8 die Wurzel - 4,2,1 sind die Ebenen. Aber wenn Sie die Wurzel auch als eine Ebene hinzufügen möchten, dann ist die Antwort logb^n + 1. –

Danke @ Sneha.Also habe ich A^und Log (Log b n). Aber wie ** a^(log b n) ** wird ** n^log (b a) ** bitte help.thanks – user5005768

Wie mathematisch ableiten Höhe und Anzahl der Blätter dieser Rekursionsbaum

Antwort

Verwandte Themen