1. 经典算法
单链表:遍历、插入、删除
循环队列:队列空、队列满的条件
二叉树:递归遍历及应用
有序表的二分法查找
快速排序
简单选择排序
1.算法:算法是为了解决某类问题而规定的一个有限长的操作序列一个算法必须满足
1.有穷性:在执行有穷步骤之后一定能结束,即算法中的每个步骤都能在有限的时间内完成
数据结构主要指逻辑结构和物理结构
数据之间的相互关系称为逻辑结构。通常分为四类基本结构: 一、集合
结构中的数据元素除了同属于一种类型外,别无其它关系。 二、线性结构
结构中的数据元素之间存在一对一的关系。 三、树型结构
结构中的数据元素之间存在一对多的关系。 四、图状结构或网状结构
结构中的数据元素之间存在多对多的关系。
同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分
析的目的在于选择合适算法和改进算法。
算法复杂度分为时间复杂度和空间复杂度。其作用:
时间复杂度是度量算法执行的时间长短;而空间复杂度是度量算法所需存储空间的大小。
1、时间复杂度 1.1 时间频度
一个算法中的语句执行次数称为语句频度或时间频度。记为T(n) 1.2 时间复杂度
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某
个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(
n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))
为算法的渐进时间复杂度,简称时间复杂度。
在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间
频度不相同时,时间复杂度有可能相同,如
T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。
按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n),
线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。
随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
2、空间复杂度 一个算法的空间复杂度(Space
Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间
复杂度也常常简称为空间复杂度。
一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,
算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个
方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表
由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间
与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法
在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时
工作单元,而且不随问题规模的大小而改变
一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包
括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空
间两个部分。若一个算法为递归算法,其空间复杂度为递归所使用的堆栈空间的大小
,它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次
数加1,这个1表不开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的
形式给出。如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改
变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表
示为0(10g2n);当一个算法的空I司复杂度与n成线性比例关系时,可表示为0(n).若形
参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个
机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它
来存储对应实参变量的地址,以便由系统自动引用实参变量。
对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间
复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,
当=i自求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用
较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当
设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算
法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素
,才能够设计出比较好的算法
1.4 算法和算法分析
算法:是对特定问题求解步骤的一种描述
算法是指令的有限序列,其中每一条指令表示一个或多个操作。
算法具有以下五个特性:
(1)有穷性 一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。
(2)确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。
(3)可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
4)输入 一个算法有零个或多个输入,这些输入取自于某个特定的对象集合。
5)输出 一个算法有一个或多个输出,这些输出是同输入有着某些特定关系的量。
1.4.2 算法设计的要求
评价一个好的算法有以下几个标准:
(1) 正确性(Correctness ) 算法应满足具体问题的需求。
(2)可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解。
(3)健状性(Robustness) 算法应具有容错处理。当输入非法数据时,算法应对其作出反应,而不是产年莫名其妙的输出结果。
分享到:
相关推荐
严蔚敏数据结构C语言版本_可运行源码_完全C语言代码实现 ----- 毕业设计,课程设计,项目源码均经过助教老师测试,运行无误,欢迎下载交流 ----- 下载后请首先打开README.md文件(如有),某些链接可能需要魔法打开...
清华大学出版的 《数据结构 C语言》 严蔚敏主编清华大学出版的 《数据结构 C语言》 严蔚敏主编清华大学出版的 《数据结构 C语言》 严蔚敏主编清华大学出版的 《数据结构 C语言》 严蔚敏主编清华大学...
在本主题中,我们将聚焦于严蔚敏教授的数据结构C语言版第一章课件,主要涵盖数据结构的基础知识以及C语言实现的排序算法。 一、数据结构基础 数据结构可以分为两大类:线性结构和非线性结构。线性结构包括数组、...
"数据结构C语言描述课后答案(部分)+耿国华"这个资料集很可能包含了耿国华教授关于数据结构课程的一些讲解和课后习题的解答,对于学习者来说是宝贵的参考资料。 1. **链表**:链表是一种线性数据结构,其元素在...
数据结构C语言版期末考试试题(有答案) 数据结构C语言版期末考试试题(有答案) 数据结构C语言版期末考试试题(有答案) 数据结构C语言版期末考试试题(有答案)
严蔚敏数据结构c语言版光盘文件
数据结构是计算机科学中的核心课程,...因此,"数据结构C语言"不仅是计算机科学专业学生的基础课程,也是专业开发人员提升技能的必要途径。通过深入理解数据结构和算法,我们可以更好地设计和实现复杂的问题解决方案。
数据结构C语言版 PPT数据结构C语言版 PPT数据结构C语言版 PPT数据结构C语言版 PPT数据结构C语言版 PPT数据结构C语言版 PPT数据结构C语言版 PPT数据结构C语言版 PPT数据结构C语言版 PPT数据结构C语言版 PPT数据结构...
《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参数教材。 本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用;后半部分主要讨论查找和...
数据结构c语言版严蔚敏ppt
单链表(数据结构C语言版) 链表的创建,插入,删除,排序等操作并建立有菜单,可以选择操作
清华大学数据结构C语言习题集答案完全版,是学好数据结构的最佳题目库
C语言是一种强大的、低级的编程语言,非常适合实现这些数据结构,因为它允许直接访问内存,提供了底层控制。本资料“数据结构 C语言版 word”是一个针对学习者设计的文档,特别是对已经有一定C语言基础的人。 在...
本教程“零基础学数据结构C语言代码”专为初学者设计,旨在帮助他们通过实践来理解和掌握数据结构的基本概念。 首先,我们要了解数据结构的基本类型,如数组、链表、栈、队列、树和图等。数组是最基本的数据结构,...
本资源“数据结构C语言版习题与答案3”是针对这一主题的一份学习资料,旨在帮助学习者深入理解和掌握数据结构的相关概念及其C语言实现。 首先,我们要明白数据结构的基本类型,包括线性结构(如数组、链表)、树形...
这份“数据结构C语言描述”教案是针对学习者深入理解数据结构与C语言结合应用的宝贵资源。 1. **数组**:数组是最基本的数据结构,它是一系列相同类型元素的集合,可以通过索引来访问每个元素。在C语言中,数组是...
数据结构C语言版答案 严蔚敏数据结构C语言版答案 严蔚敏数据结构C语言版答案 严蔚敏数据结构C语言版答案 严蔚敏
这里我们将围绕“数据结构C语言实现”的主题,结合清华严蔚敏教授的经典教材,详细讨论相关知识点。 首先,严蔚敏教授的《数据结构》是学习数据结构的经典参考书,书中涵盖了线性结构、树形结构、图结构以及查找和...
数据结构c语言课程设计图书管理系统.zip数据结构c语言课程设计图书管理系统.zip数据结构c语言课程设计图书管理系统.zip数据结构c语言课程设计图书管理系统.zip数据结构c语言课程设计图书管理系统.zip数据结构c语言...
《严蔚敏数据结构C语言版》是一本深入讲解数据结构的经典教材,它以其严谨的理论和实用的C语言实现闻名。数据结构是计算机科学中的核心课程,它研究如何高效地存储、组织和操作数据,为算法设计和分析提供基础。这...