Name: Password: Sign in
Data Structures and Algorithm Analysis Notes 中的文章
  • [Lecture 1] Introduction, Mathematics Review, Recursion
  • [Lecture 2] Asymptotic Notation, Algorithm Analysis
  • 本文在 署名-非商业性使用-相同方式共享 3.0 版权协议下发布, 转载请注明出自 kyleslight.net

    [Lecture 1] Introduction, Mathematics Review, Recursion

    1 Foreword

    This tutorial is written down as notes for a classic book Data Structures and Algorithm Analysis in C, most of the big ideas and programming code of my notes can be found in the source of this book.

    We may have used a number of data structures, in some languages, such as Python, it would be possible for us to get familiar with tuple, array, dictionary and customized data structures, but we may get confused about the behaviour and the performance of those data structures while using them and have no deep idea about why we have to choose the appropriate one, though sometimes others seem to work fine as well.

    This notes is created for the aim to enhance the concepts of those data structures and algorithms. We will see some implementations in C\C++ driven by the ideas behind them, during the process, those ideas will make us have a deep thought about : why they designed in this way, how they performance and what we can do to reduce the complexity of algorithm and make a better one.

    2. Mathematics Review

    There are some of the fundamental math facts to be reviewed:

    2.1 Series

    0NAi=AN+11A1

    The proof shows below :

    S=1+A+A2+...+AN

    AS=A+A2+...+AN+1

    (A1)S=AN+11

    S=AN+11A1

    Further more, If 0<A<1, When N goes to , we have :

    0Ai=11A

    There are other facts in arithmetic series:

    1Ni=(N+1)N2N22

    1Ni2=N(N+1)(2N+1)6N33

    ...

    1NikNk+1|k+1|

    When k=1

    1N1ilogeN

    2.2 Proof by Induction

    Suppose that we have Fibonacci Sequence, we want to know how big the item is with the growth of N . And here is a hypothesis :

    FN<(53)N

    To use induction, we need to take the following steps:

    • Proving the base case (usually when n=1 or 2)
    • Inductive hypothesis is assumed (assuming n=k the theorem is true)
    • Proving the theorem is true in the next value of k

    Back to our Fibonacci Hypothesis:

    N=1,F1=1<(53);N=2,F2=1<(259)

    We have proved the basis. Next we assume that when N=k, this hypothesis is true. That is :

    Fk<(53)k

    Naturally, when N=k+1 :

    Fk+1=Fk+Fk1

    Fk+1=(53)k+(53)k1

    Fk+1=(35)(53)k+1+(925)(53)k+1

    FK+1=(2425)(53)k+1<(53)k+1

    Theorem proved.

    The process of induction is inspiring for its principle : Make sure that the basis is satisfied with the theorem, every time we prove the N=k+1 case, we just return back to see if N=k the result is right; Then we will turn back again and again until we see our basic case, and that’s why we guarantee the basic case to be true at first.

    In fact, the idea “again and again” can be used in a number of problems, in which we will find a main problem contains several sub-problems, and the sub-problem have the same structure with the big one ( in other case it contains no sub-problem and can be solved directly ), and that’s why we introducing Recursion.

    3. Recursion

    Mathematical functions can sometimes be defined in this way :

    f(x)=2×f(x1)+3

    In which, to determine the value of f(x) we have to look for the value of f(x1), and repeat this process until we get some condition to stop, then we pass the value back again and again, finally get our f(x).

    Here’s a brief example showing how to get value of aN using Recursion :

    int Pow (int a, int n) {
        if(n == 0) return a;
        return Pow(a, n - 1) * n;
    }
    

    This is a bad implementation, of course. We will discuss about it in our next tutorial. But at least it works when the given input n is not too large, and it shows an intuitive method to reduce the input and get the direct result in basic condition.

    Recursion is powerful as it’s really efficient to express your mind, but it should be used carefully as it will sometimes make your program run out of time; In other case, you also should take care about your basic condition to make sure every time when get to function call, the parameter will be closer to terminal condition. If the user give a negative number, the program above will never end and turn crashed.

    Copyright (c) 2014-2016 Kyles Light.
    Powered by Tornado.
    鄂 ICP 备 15003296 号