数据结构 - 1 基本概念

2020/4/10 0:15:34 人评论 次浏览 分类:学习教程

数据结构

  • 1 基本概念
    • 1.1 什么是数据结构
      • 什么是数据结构
      • 抽象数据类型
    • 1.2 什么是算法
      • 什么是好算法
        • 时间复杂度T(n)
        • 空间复杂度S(n)

1 基本概念

1.1 什么是数据结构

例2 传入一个正整数N,顺序打印从1到N的全部正整数:

//递归实现
void PrintN(int N){
	if(N){
		PrintN(N-1);
		printf("%d\n",N);
	}
}

递归程序占用空间大
解决问题方法的效率,跟空间的利用效率有关
在这里插入图片描述
第2个函数标准
在这里插入图片描述
使用clock()来测试程序运行时间

但是,有的程序跑完所用时间会很小,约等于0,此时,可以重复执行程序

什么是数据结构

在这里插入图片描述
逻辑结构:线性结构(一对一)、树(一对多)、图(多对多)
物理存储结构:在计算机中是用数组来存还是链表来存

抽象数据类型

在这里插入图片描述
在这里插入图片描述
对于a是float还是double都不管,ElementType就是a的类型

1.2 什么是算法

在这里插入图片描述

什么是好算法

时间复杂度T(n)

根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。过高会导致等不到结果。

空间复杂度S(n)

根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。过高会导致使用的内存超限,造成程序非正常中断。
在这里插入图片描述
递归每次调用时都会占用一定的内存空间来存储信息,而for循环只用了临时变量和for循环,没有设计任何程序调用的问题,所以他占用的空间是个常量。
在这里插入图片描述
在这里插入图片描述
例子:
在这里插入图片描述
算法1:暴力法。三层嵌套for循环,可以证明是1个N3 * 1个常数
在这里插入图片描述
由上图可知,当知道i到j之和时,再加1个数就可以了,所以k那个循环可以省略
在这里插入图片描述
要尽可能的把n2 改进为nlogN

算法3:分治法,把1个比较大的复杂的问题切分成小的块,然后分头去解决它们,最后再把结果合并起来
在这里插入图片描述把它分成2部分,左半部分递归查找最大的,右半部分递归查找最大的,在查找中间部分最大的
在这里插入图片描述
计算时间复杂度:想象,当解决的整个问题里有N个数字的时候,如果复杂度记作T(N),那么可得半边数字的复杂度为T(N/2),因为规模减半了。
红色的中间部分:因为要从中间扫描左边然后扫描右边,每一个元素都被扫描了1次,所以复杂度应该是N的一个常数倍
在这里插入图片描述
在这里插入图片描述
正确性不是很明显(不好理解)
在这里插入图片描述
在这里插入图片描述

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->