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

$\sum _{0}^{N}{A}^{i}=\frac{{A}^{N+1}-1}{A-1}$

The proof shows below :

$S=1+A+{A}^{2}+...+{A}^{N}$

$AS=A+{A}^{2}+...+{A}^{N+1}$

$\left(A-1\right)S={A}^{N+1}-1$

$S=\frac{{A}^{N+1}-1}{A-1}$

Further more, If $0, When $N$ goes to $\mathrm{\infty }$, we have :

$\sum _{0}^{\mathrm{\infty }}{A}^{i}=\frac{1}{1-A}$

There are other facts in arithmetic series:

$\sum _{1}^{N}i=\frac{\left(N+1\right)N}{2}\approx \frac{{N}^{2}}{2}$

$\sum _{1}^{N}{i}^{2}=\frac{N\left(N+1\right)\left(2N+1\right)}{6}\approx \frac{{N}^{3}}{3}$

$...$

$\sum _{1}^{N}{i}^{k}\approx \frac{{N}^{k+1}}{|k+1|}$

When $k=-1$

$\sum _{1}^{N}\frac{1}{i}\approx {\mathrm{log}}_{e}N$

### 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 :

${F}_{N}<{\left(\frac{5}{3}\right)}^{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,{F}_{1}=1<\left(\frac{5}{3}\right);N=2,{F}_{2}=1<\left(\frac{25}{9}\right)$

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

${F}_{k}<{\left(\frac{5}{3}\right)}^{k}$

Naturally, when $N=k+1$ :

${F}_{k+1}={F}_{k}+{F}_{k-1}$

${F}_{k+1}={\left(\frac{5}{3}\right)}^{k}+{\left(\frac{5}{3}\right)}^{k-1}$

${F}_{k+1}=\left(\frac{3}{5}\right){\left(\frac{5}{3}\right)}^{k+1}+\left(\frac{9}{25}\right){\left(\frac{5}{3}\right)}^{k+1}$

${F}_{K+1}=\left(\frac{24}{25}\right){\left(\frac{5}{3}\right)}^{k+1}<{\left(\frac{5}{3}\right)}^{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\left(x\right)=2×f\left(x-1\right)+3$

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

Here’s a brief example showing how to get value of ${a}^{N}$ 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.