数据结构---学习笔记（一）

        第一章 绪论

        1 大O记号：
       
        1.1 大O记号
              大O记号是时间复杂度的一种刻度，起始是一种趋势的表示。而时间复杂度描述的则是程序执行的次数，等价运行时间。
              关于时间复杂度：
              T(n) = O( f(n) )，f(n)是一个函数，T(n)就表示时间复杂度；
       
        1.2 刻度--高效解
            1.2.1 常数O(c)
                例如程序运行的次数是一个常数，则对于大O记号来书，有如下等式：
                2=2013=2013*2013=O(1)甚至是2013²⁰¹³=O(1)；
                怎么理解这个O(1)呢？假设现在有一个坐标轴，横轴表示时间，纵轴表示运算成本(次数)。那对于运算成本(次数)为常数的程序说随
        着时间的不断增加，其运算成本是不会改变的。不过这是一种理想状态。
                而什么样的代码段对应于这样一个刻度呢？有以下三个条件：
                a)一定不含循环；
                b)一定不含分之转向；
                c)一定不含调用和递归；
            1.2.2 对数O(logn)
                a)常底数无所谓
                对于任意的常数a,b,都有：log_an=log_ab*log_bn=O(log_bn)；
                b)常数次幂无所谓
                对于任意的c>0，都有：(logn)c=c(logn)=O(logn) ；
                c)对于多项式
                123*log³²¹n+log¹⁰⁵(n2-n+1)=O(log³²¹n)；
                之前讲过，大O记号表示一种趋势，如果是O(logn)，再想想之前讲得坐标轴。随着时间的增加，计算成本趋近与一个平稳的值；

        1.3 刻度--有效解
              有效解就是O(n^k)，表示一个多项式。
              如果代码段的计算成本为f(n) = a_kn^k+......+a_0，那该代码段的时间复杂度可以被标记为O(n^k)，取最高次项。同理，可以想象一下那个
             坐标轴，想想n^k的函数曲线。想象一下大概的趋势。
    
        1.4 刻度--难解
              难解指的是f(n) = aⁿ,其中a为常数，这类计算成本是不能被接受的。
         
              综上所述，应有如下等式：
              对于任意的c>1，有n^c=O(2ⁿ)   
                                    n¹⁰⁰⁰=O(1.00000001ⁿ)=O(2ⁿ)     //即多项式的成本永远都低于指数的成本，指数构成了一个上界
              截图一张，能够清晰的看出各个刻度对应代码段运算成本的关系：

        

        2 迭代和递归------这里就不多作叙述了，如果不了解的朋友可以看看：
            http://blog.csdn.net/swliao/article/details/5337896

          
        3 动态规划
                  动态规划的含义就是：利用递归的方法按要求实现代码，因为对于递归来说一般都是可以实现的，以运算成本为代价，然后找
           出原理，然后用迭代的方法实现。例子有一个LCS最长公共子序列。             
           递归的源代码：
           

/*
 *lcs_recursion.c
 *description:realize the lcs by recursion
 *By HG
 *2015-4-8
 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int lcs(char str_a[],int a_length,char str_b[],int b_length)
{

    if(a_length == -1 || b_length == -1)
    {
        return 0;
    }
    if(str_a[a_length]==str_b[b_length])
    {

        return lcs(str_a,--a_length,str_b,--b_length) + 1;
    }
    else
    {
        return lcs(str_a,--a_length,str_b,b_length)>lcs(str_a,a_length,str_b,--b_length)?lcs(str_a,--a_length,str_b,b_length):lcs(str_a,a_length,str_b,--b_length);
    }
}

int main(void)
{
    char a[]="tsinghua";
    char b[]="sina";
    int lcs_length;

    lcs_length = lcs(a,strlen(a)-1,b,strlen(b)-1);

    printf("the LCS of a and b is %d\n",lcs_length);

    return 0;
}

           迭代的源代码：

#include<stdio.h>
#include<string.h>

#define ARRAY_LEN 20

int max(int a,int b)
{
        return a>b ? a:b;
}

int main()
{
        int array[ARRAY_LEN][ARRAY_LEN]={0};
        int a_len,b_len;
        int i,j;
        char *str_a="tsinghua";
        char *str_b="sina";

        a_len = strlen(str_a);
        b_len = strlen(str_b);


        for(i=0;i<a_len;i++)
        {
                for(j=0;j<b_len;j++)
                {
                        if(str_a[i]==str_b[j])
                                array[i+1][j+1]=array[i][j]+1;
                        else
                                array[i+1][j+1]=max(array[i+1][j],array[i][j+1]);
                }
        }

        for(i=0;i<a_len+1;i++)
        {
                for(j=0;j<b_len+1;j++)
                {
                        printf("%d\t",array[i][j]);
                }
                printf("\n");
        }

        return 0;
}