算法概论 -- Chapter 0 Prologue

Fibonacci numbers:

 

Introduction :
          F(n) = F(n-1) + F(n-2) , for n >= 2,  and F(0) = 0,  F(1) = 1
          One approximation of F(n) is roughly , now I'm gonna prove it first.

 

          Promble: Find a constant c < 1 such that F(n) <=  for all n >= 0 , and find the minimal c.

          proof :  We use induction to prove it and intuitively we can guess what is c. 

                      Suppose F(n) <=  ,  then we need to show F(n+1) <=   which means that  +  <=  . Solve this inequlity we get c >=  , the following steps is simple, I'll leave it out.

 

          Then what does this approximation means? It means that the bit-length of F(n) is roughly 0.694n. So for a 32-bit machine, the word size is far less than F(n) , the arithmetic operation on F(n) cann't be considered as O(1) time given the bit-length.

 

        These are three ways to calculate Fibonacci:

 

        1. An exponential algorithm:

            

def fib1(n):
    """
    This function calculates fibonacci series.
    It takes exponential time.
    """
    
    if n <= 0 :
        return 0
    elif n == 1 :
        return 1
    else:
        return fib1(n-1) + fib1(n-2)

 

 

     Running time analysis: T(n) = T(n-1) + T(n-2) +  3 , for n > 1. obviously T(n) >= F(n) which grows exponentially.

 

       2. a Polynomial algorithm

       

def fib2(n):
    """
    This function calculates fibonacci series.
    It takes linear time.
    If n is too large, it takes roughly quadratic time.
    """
    if n == 0 :
        return 0
    res = []
    res.append(0)
    res.append(1)
    for i in range(2,n+1):
        res.append(res[i-1] + res[i-2])
    return res[n]

 

 

    Running time analysis: it's easy to see that it has reduced many redundant recurrences, the running time depends on the execution time of (res[i-1] + res[i-2]).

    if res[i] is within machine word-length, it takes O(1) time, and the total time is O(n)

    But if res[i] is beyond machine word-length, it takes O(  ) time and the total time is O(n*  )   = O( ) which is polynomial to n.

 

          3. A log time algorithm 

          

import numpy as np

def quick_power(a,n):
    """
    This function calculates a to the power of n.
    It takes log time. 未处理0的情况
    """
    if n == 1:
        return a
    elif n== 2:
        return a * a
    elif n % 2 == 0:
        temp_res = quick_power(a, n/2)
        return temp_res * temp_res
    else:
        temp_res = quick_power(a, (n-1)/2)
        return temp_res * temp_res * a
        

def fib3(n):
    """
    This function calculates fibonacci series.
    It takes log time.
    """
    origin = np.matrix([[1,1], [1,0]])
    res = quick_power(origin, n)
    
    return res[0, 1]

   

       Running time analysis:  This algorithm use an fact that : 

       We use quick_power to do n-power operation for O(log n) time, but there are some problem in it. We do 8 mulplications in matrix mulplication rather than simple addition. As you know, multiplication may take more time than addition, so when n is large ,  it needs further analysis.  This part isn't completed.

 

       Finally this is the running result of above 3 algorithms: Red : fib1 ,  blue : fib2,  grenn : fib3 , y-axis: time, x-axis : n. 

 

       

 

 

       

[list=1][list=1][list=1]

[/list]

[/list]

[/list]