小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Computer & DL
  4. Data Structure
  5. 正文

数据结构【浙江大学】(第1节)整理

2018年4月3日 1794点热度 0人点赞 2条评论

第一节:数据结构基本知识

1.1 什么是数据结构

例:写程序实现一个函数PrintN,使得传入一个正整数位N的参数后,能顺序打印从1道N的全部正整数。

代码1(循环实现):

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

代码2(递归实现):

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

结论:解决问题方法的效率,跟空间的利用率有关。

例3:写程序计算给定多项式在给定点x处的值

代码:

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;
}

C语言中提供了一个函数为clock(),它捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时钟单位是clock tick。常熟CLK_TCK为机器时钟每秒所周的clock tick。例子如下:

#include <stdio.h>
#include <time.h>
clock_t start,stop;
/*clock_t是clock()函数返回的变量类型*/
double duration;
 
int main()
{
       start = clock();
       MyFunction();//所需要测量运行时间的函数
       stop = clock();
       duration = ((double)(stop-start)/CLK_TCK;
       return 0;
}

结论:解决问题方法的效率,跟算法的巧妙程度有关。

什么是数据结构?

数据对象在计算机中的组织方式。数据对象必定与一系列加在其上面的操作相关联,完成这项操作所用的方法就是算法。

抽象数据类型

抽象是指:描述数据类型的方法不依赖与具体事项,它:

①与存放数据的机器无关;②与数据存储的物理结构无关;③与实现操作的算法和编程语言均无关。

它只描述数据对象集和相关操作集“是什么”,并不涉及“如何做”的问题。

1.2 算法

1.什么是算法?

算法是:

(1)一个有限指令集;

(2)接受一些输入(有时候也没有输入);

(3)产生输出;

(4)一定在有限步骤后终止;

(5)每一条指令必须:有充分明确的目标,不可以有歧义;计算机能够处理的范围之内;描述应不依赖于任何一种计算机语言以及具体的实现。

2.什么是好的算法?

在分析一般算法的效率时,我们经常关注一下两种复杂度:

(1)最坏情况复杂度Tworst(n);

(2)平均复杂度Tavg(n)。

3 复杂度的渐进表示法

T(n)=O(f(n))表示存在常数C>0,n0>0使得当n≥n0时有T(n)≤Cf(n);

T(n)=Ω(f(n))表示存在常数C>0,n0>0使得当n≥n0时有T(n)≥Cf(n);

T(n)=θ(h(n))表示同时又T(n)= O(f(n))和T(n)=Ω(f(n))。

不同复杂度函数的感性理解,如表1.1所示。

1.1 不同复杂度函数的规模

函数

1

2

4

8

16

32

1

1

1

1

1

1

1

logn

0

1

2

3

4

5

n

1

2

4

8

16

32

nlogn

0

2

8

24

64

160

n2

1

4

16

64

256

1024

n3

1

8

64

512

4096

32768

2n

1

4

16

256

65536

4294967296

n!

1

2

24

40326

2092278988000

26313*1033

如果复杂度为灰色斜体的部份,要想办法尽可能降到黑色部分。

复杂度分析小窍门:

(1)若两段算法分别有复杂度T1(n)=O(f1(n))和T2(n)=O(f2(n)),则

①两段代码的和T1(n)+T2(n)=max(O(f1(n)), T2(n)=O(f2(n)))

②两段代码嵌套起来T1(n)×T2(n)=O(f1(n)×f2(n))。

(2)若T(n)是关于n的k阶多项式,那么T(n)= θ(nk)。

(3)一个for循环的时间复杂度等于循环次数乘循环体内代码的复杂度。

(4)if-else结构的复杂度取决于if的条件判断复杂度和两个分枝部分的复杂度,总体复杂度取三者中最大。

1.3 应用实例

1.例1

1522767675424103.jpg

复杂度为O(N3)

算法2:

int MaxSubseqSum2(int A[], int N)
{
       int ThisSum, MaxSum=0;
       int i ,j;
       for(i=0;i<N;i++)/*i是子列左端的位置*/
       {
              ThisSum =0;/*ThisSum是从A[i]dao A[j]的子列和*/
              for(j=i; j<N;j++)
              {
                     ThisSum+=A[j];
                     /*对于相同的i,不同的j,只要把j-1此循环的基础上累加1项即可*/
                     if(ThisSum>MaxSum)
                     MaxSum=ThisSum;
              }
       }
       return MaxSum;
}

复杂度为O(N2)

算法3:分而治之

先将这个数组分为两半,分别递归的解决两边的问题。在左边我们会得到一个左边的最大值,右边会得到一个右边的最大值,然后再求一个跨越边界的最大子列和。然后对其进行比较,寻找到最大值。

1522767648119445.jpg 

图2

算法4:在线处理

代码:

int MaxSubseqSum4(int A[], int N)
{
       int ThisSum, MaxSum;
       int i;
       ThisSum=MaxSum=0;
       for(i=0;i<N;i++){
              ThisSum +=A[i];/*向右累加*/
              if(ThisSum>MaxSum)
                     MaxSum=ThisSum;/*发现更大和则更新当前结果*/
              else if(ThisSum<0)/*如果当前子列和为负*/
                  ThisSum=0;/*则不可能使后面的部分和增大,抛弃之*/
       }
       return MaxSum;
}

复杂度为O(N)

为了理解这个算法,举个例子来走一遍过程。假设一组数字为:

序号

0

1

2

3

4

5

6

7

取值

-1

3

-2

4

-6

1

6

-1

刚开始,我们就令ThisSum和MaxSum为0。进入for循环。

i取值

步骤

ThisSum

MaxSum

0

ThisSum为-1,-1<0,故抛弃这个值

0

0

1

然后ThisSum加上A[1],由于之前ThisSum令为0了,所以现在值为3。然后ThisSum>MaxSum,所以把ThisSum赋值给MaxSum,后者等于3。

3

3

2

然后ThisSum加上A[2],当前和为+1,然后MaxSum>ThisSum,所以不赋值,由于ThisSum为+1,故不抛弃。

+1

3

3

ThisSum加上A[3],结果为5,然后ThisSum>MaxSum,所以把ThisSum赋值给MaxSum,后者等于5

+5

5

4

ThisSum加上A[4],结果为-1。此时ThisSum小于MaxSum,所以不改变Max的值。又由于This<0,故赋值为0。

0

5

5

ThisSum加上A[5],值为1,此时ThisSum小于MaxSum,所以不改变Max的值。

1

5

6

ThisSum加上A[6],值为7,此时ThisSum大于MaxSum,所以把ThisSum赋值给MaxSum,后者等于7

7

7

7

ThisSum加上A[7],值为6,此时ThisSum小于MaxSum,所以不改变Max的值。

6

7

 

故最大值为7。

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 何钦铭 数据结构 浙江大学 陈越
最后更新:2018年4月3日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

  • 匿名

    真有才啊,看看自己的排版成啥样了

    2020年4月9日
    回复
    • 小奥

      @匿名 时间很久了,之前的文档都没有去管理了,发现github上的文件都挂了 = =

      2020年4月30日
      回复
  • razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
    取消回复

    搜索
    欢迎关注我的个人公众号
    最新 热点 随机
    最新 热点 随机
    DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
    奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
    『超决战!奥特英雄传说』新版官方网站正式启用! Java数据库设计入门 悲剧了~ 每日一感0920:相信自己·Belive myself 2010 S.V Beijing Travel 3~4:唉 出道两年来自己的一些感悟
    标签聚合
    学习 鸟哥的linux私房菜 leetcode 算法 Java 生活 python学习 linux 高中 Python
    最近评论
    davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
    tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
    cuicui 发布于 9 个月前(10月20日) :wink:
    niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
    davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
    Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
    davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
    aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
    匿名 发布于 5 年前(12月30日) 烫
    小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

    COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

    Theme Kratos Made By Seaton Jiang

    陕ICP备19003234号-1

    鲁公网安备37120202000100号