数据结构课上笔记2

举报
兔老大 发表于 2021/04/20 00:42:30 2021/04/20
【摘要】 今天继续说明了一些基本概念,讲解了时间空间复杂度。 (对于概念的掌握也很重要)   元素之间的关系在计算机中有两种表示方法:顺序映像和非顺序映像,由此得到两种不同的储存结构: 顺序存储结构和链式存储结构。   顺序:根据元素在存储器中的相对位置表示关系 链式:借助指针表示关系   数据类型:是一个值的集合和定义在这个值集上的一组...

今天继续说明了一些基本概念,讲解了时间空间复杂度。

(对于概念的掌握也很重要)

 

元素之间的关系在计算机中有两种表示方法:顺序映像和非顺序映像,由此得到两种不同的储存结构:

顺序存储结构和链式存储结构。

 

顺序:根据元素在存储器中的相对位置表示关系

链式:借助指针表示关系

 

数据类型:是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型:是指一个数学模型以及定义在该模型上的一组操作。(仅仅取决于逻辑特性,与其在计算机内部如何表示和实现无关)

 

定义抽象数据类型的一种格式:

ADT name{

数据对象:<>

数据关系:<>

基本操作:<>

}ADT name

 

算法:是对特定问题求解步骤的一种描述。

算法五个特性:

  1. 有穷性:有穷的时间内完成,或者可以说是可接受的时间完成
  2. 确定性:对于相同的输入只能得到相同的输出
  3. 可行性:描述的操作都可以执行基本操作有限次来实现
  4. 输入:零个或多个输入。取自于某个特定对象的集合
  5. 输出:一个或多个输出

 

设计要求:正确性、可读性、健壮性、效率与低存储量需求。

执行频度概念:是指通过统计算法的每一条指令的执行次数得到的。

执行频度=算法中每一条语句执行次数的和

一般认定每条语句执行一次所需时间为单位时间(常数时间)O(1)

 

几个小知识和小问题:

1)循环执行次数n+1次,不是n次。第一次执行i=1和判断i<=n以后执行n次判断和i++。所以该语句执行了n+1次。在他的控制下,循环体执行了n次。

2)四个并列程序段:分别为O(N),O(N^2),O(N^3),O(N*logN),整个程序时间复杂度为O(N^3),因为随着N的增长,其它项都会忽略

3)算法分析的目的是分析算法的效率以求改进

4)对算法分析的前提是算法必须正确

5)原地工作指的不是不需要空间,而是空间复杂度O(1),可能会需要有限几个变量。

实现统一功能两种算法:时间O(2^N),O(N^10),假设计算机可以运行10^7秒,每秒可执行基本操作10^5次,问可解问题规模各为多少?选哪个更为合适?

计算机一共可执行10^7*10^5=10^12次

第一种:n=log2,(10^12)=12log(2,10)

第二种:n=(10^12)^0.1

显然1更适用。

虽然一般情况多项式算法比指数阶更优

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/82700455

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200