[combinatorial mathematics] recursive equation (example of recursive equation 2 Hanoi Tower | example of recursive equation 3 insertion sequencing)

One 、 Examples of recursive equations 2 Hanoi

---

Hanoi problem :

• The recurrence equation is :$T(n)=2T(n-1)+1$
• initial value :$T(1)=1$
• Explain :$T(n)=2^n-1$

The recurrence equation represents , take

n

n

n The number of times a plate moves

T

(

n

)

T(n)

T(n) , And

n

−

1

n-1

n−1 The number of times a plate moves

T

(

n

−

1

)

T(n-1)

T(n−1) The relationship between ;

Solution reference : 【 Combinatorial mathematics 】 Recurrence equation ( Examples of special solutions ) One 、 Special solution example 1 ( Hanoi )

Two 、 Examples of recursive equations 3 Insertion sort

---

W

(

n

)

W(n)

W(n) Indicates the number of times to insert a sort in the worst case ;

Ahead

n

−

1

n-1

n−1 The number has been arranged , In the worst case, the number of insertion sorts is

W

(

n

−

1

)

W(n-1)

W(n−1) Time ,

The first

n

n

n A number should be inserted here

n

−

1

n-1

n−1 Of the numbers , The worst case scenario is The number to be inserted should be the same as all the sorted numbers

n

−

1

n-1

n−1 Compare two numbers , The number of comparisons is

n

−

1

n-1

n−1 Time ,

So the recurrence equation can be written as :

W

(

n

)

=

W

(

n

−

1

)

+

n

−

1

W(n) = W(n-1) + n-1

W(n)=W(n−1)+n−1

Initial value of recurrence equation :

W

(

1

)

=

0

W(1) = 0

W(1)=0 , If there is only one number , No sorting , The number of comparisons is

0

0

0 ;

The final solution is :

W

(

n

)

=

O

(

n

2

)

W(n) = O(n^2)

W(n)=O(n2) , The exact value is

W

(

n

)

=

n

(

n

−

1

)

2

W(n) = \cfrac{n(n-1)}{2}

W(n)=2n(n−1)​