数据结构-浙大 MOOC 笔记一 基本概念

做一些笔记记录自己的学习过程

第一节课介绍了数据结构的基本概念，首先没有直接给出相关的定义而是通过思考如何在书架上摆放书籍这样一个简单的类比了解到数据的组织方式的重要性，并通过printN函数的循环实现和递归实现的差异来说明解决问题方法的效率跟空间的利用效率有关，计算多项式在某一个给定点处的值来说明解决问题方法的效率与算法的设计有关。

void PrintN(int N)
{int i;
 for (i=1;i<=N;i++){
　　printf("%d
",i);
}
return;
}

//循环实现

void PrintN (int N)
{
if (N){
    PrintN(N-1);
    printf("%d
",N);
    }
    return;
}

//递归实现

　　

double f( int n, double a[], double x)
{ int i;
   double p=a[0];
   for (i=1; i<=n; i++)
        p+= (a[i]* pow(x,i));
    return p;
}

//循环实现

double f( int n, double a[], double x)
{ int i;
   double p= a[n];
   for (i=n; i>0; i--)
      p = a[i-1] + x*p;
   return p;
}

//递归实现

 在进行算法分析和比较的过程中，我们会有实际进行程序运行时间的计算内容，这就需要用到clock()函数；

运行的模板如下

int main ()
    start = clock();
    MyFunction()；
    stop= clock();
    duration = ((double) (stop= start)) / CLK_TCK

其中CLK_TCK 表示机器时钟每秒所走的时钟打点数

自然推导出相关的结论说明数据结构是关于 对象结构+操作+算法三个部分的内容

第一讲的最后又简单介绍了抽象数据类型的定义 (Abstract Data Type)

数据对象集 + 数据集合相关联的操作集

抽象表示实现方法不依赖于具体实现，under the hood部分的内容不做考虑，只关心开车不关心怎么造汽车的一个过程。

比如矩阵作为一种抽象数据类型

可以从以下几点来考虑

1.2 什么是算法？

• 有限的指令
• 接受一些输入
• 产生输出
• 在有限步骤之后终止
• 每一条指令必须 a.明确 b.计算机可处理 c.不依赖单独某一种特定的计算机语言

时间复杂度 与 空间复杂度的计算技巧

for 循环则相乘

if- else 取决于if条件判断复杂度和两个分枝部分的复杂度三者中的最大值

T1(n) + T2(n) = max 

T1(n) * T2(n) = O (f1(n)*f2(n))

1.3 最大子列和问题-实例分析

算法1： 累加

for (i=1; i<=n; i++){
    ThisSum=0;
    for (j=i; j<=n; j++){
        ThisSum+=A[j];
        if (ThisSum> MaxSum)
            MaxSum= ThisSum;
       }
}

算法2： 分而治之

左 中 右 

 可以达到O(nlogn) 的时间复杂度

算法3： 在线处理

for (i=0; i<N; i++) {
    ThisSum+=A[i];
    if (ThisSum> MaxSum)
        MaxSum=ThisSum;
    else if (ThisSum <0 )
        ThisSum=0;
}

根据“连续”条件作出的高效处理，如果是负数则直接舍弃，不做加和操作。

可以达到 O(n)的时间复杂度，遍历一次即可得到结果。

今天上完这门课程的第一讲，感觉课程内容还是比较简单清楚的，相比于学堂在线的MOOC数据结构，该课程难度会低一些，不过涉猎的范围会广一些，方便个人打基础。