01 - 数据结构和算法的认识
了解数据结构和算法的一些基本概念,主要掌握时间复杂度的计算
数据结构是指所有数据元素以及数据元素之间的关系,可以看做是相互之间存在着某种特定关系的数据元素的集合,即可以把数据结构看成是 带结构的数据元素的集合 。
数据的逻辑结构是从逻辑关系上描述数据的,常常将数据的逻辑结构简称为数据结构。
集合:
树形结构:
图形结构:
逻辑结构在计算机中的存储方式。依赖于计算机语言
顺序存储结构:
链式存储结构:
索引存储结构:
散列(哈希)存储结构:
数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称,数据类型是数据结构在计算机的具体体现。
注意:
算法是对特定问题求解步骤的一种描述
特性: 有穷性、确定性、可行性、有输入、有输出
算法设计好后,还需要分析算法的优劣,从两方面考虑
一个算法由控制结构和原操作构成,算法的运算时间取决于两者的综合效果,算法执行时间大致为基本运算时所需时间与运行次数的乘积。因此一个算法的执行效率可以由其最基本的运算的执行次数来衡量。
计算公式: T(n)=O(f(n))
说明:
注意: O 的作用在于只求出T(n)的最高阶项,忽略低阶项和常数
O(1)
没有进行循环的算法中,基本运算次数与问题规模无关,所以是常数
对数阶 O(log2n)
次数为x,而2的x次方等于n,那么就是对数阶
线性阶 O(n)
只有一层循环
平方阶 O(n^2)
立方阶 O(n^3)
三层循环,肯定就是n^3了
排序:
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) <O(2^n) < O(n!) < O(n^n)
也叫加权平均时间复杂度,将执行的概率也加入计算。
是一种特殊的加权平均时间复杂度,把耗时多的操作分摊到耗时低的操作。
这个时间复杂度 其实是O(1),而不是O(n)
算法空间复杂度是指计算算法所需的存储空间, 其计算公式为S(n) = n(f(n))
所以在考察算法的空间复杂度,主要考虑算法执行所需要的临时占用的存储空间大小的量度。
数组逆序,将一维v1.43数组a中的n个数逆序存放在原数组中.
复杂度计算:
说明:
布岚产后: 本人乃一个数据痴迷者,在计算机的道路上,也是一个数据结构的痴迷者,现在大学里面和同学搞开发也痴迷于数据库,我就我个人的理解给你谈一谈: 首先,数据结构是一门计算机语言学的基础学科,它不属于任何一门语言,其体现的是几乎...
金山屯区18439849732: 在C语言编程中数据结构与算法是怎么体现的,或者说怎么理解数据结构的作用? - ?
布岚产后: 举个例子,你写个程序,要存全校学生的信息. 首先学生数量可能是变动的,你不可能写成固定数组. 你可以思考下怎么存. 这时候就可以建立一个链表,在每次输入一个新生时把他挂入链表. 这样就可以遍历学生信息了. 这里只是讲数据结构对存储的作用,另外一方面是,好的数据结构,可以使算法简单,可以让程序结构清晰. 这里我想吐槽下,学校的教育模式:学生都不知道是干嘛的,干嘛要去学,还要考高分?而老师只会说:能到以后你们就会明白的,我靠.不知道学的东西是干嘛用的,我怎么想去学,怎么会有兴趣,怎么会去主动.
金山屯区18439849732: 数据结构和算法有什么关系?数据结构就是算法吗? - ?
布岚产后: 它们可以相互区别也可以相互统一.广义上讲,算法是某一系列运算步 骤,它表达解决某一类计算问题的一般方法,对这类方法的任何一个输入,它可以按步骤一步一步计算,最终产生一个输出.但是对于所有的计算问题,都离不开要 计算的...
金山屯区18439849732: 数据结构学的到底是什么?和算法有什么关系? - ?
布岚产后: 首先,数据结构是一门计算机语言学的基础学科,它不属于任何一门语言,其体现的是几乎所有标准语言的算法的思想.上面的概念有一些模糊,我们现在来具体说一说,相信你门的数据结构使用的是一门具体的语言比如C/C++语言来说明,那...
金山屯区18439849732: 数据结构是什么? - ?
布岚产后: 数据结构是在整个计算机科学与技术领域上广泛被使用的术语.它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构.数据结构有逻辑上的数据结构和物理上的数据结构之分.逻辑上的数据结构反映...
金山屯区18439849732: 算法和数据结构有什么区别 - ?
布岚产后: 其实两者可以说关联不大. 算法就是一个处理的方法,比如大学里基础的排序算法,就是为了完成对一组数据排序.查找算法,就是为了在一个集合中查找需要的项.除此之外,还有很多算法,比方说,加密、压缩、图像处理. 而数据结构就是数据的结构.比方说队列、堆、栈、链表、树等等. 大学里的《算法与数据结构》这门课是个入门的算法课和数据结构课程.教授针对不同的数据结构进行的排序、查找、遍历的不同算法.仅是算法基础,就象大学里都是以C语言作为入门语言一样的.
金山屯区18439849732: 数据结构,算法是什么意思?他们之间有什么联系? - ?
布岚产后: 数据结构指数据在计算机中存储存在的方式,比如 文件在硬盘中,有二进制,文本等形式存放, 程序中的一组数字可能放在数组里面,也可能在栈里面,也肯能在链表里面 算法就是计算机处理解决问题的计算机能理解的方法,比如算一个阶乘 ...
金山屯区18439849732: 什么是算法与数据结构 - ?
布岚产后: 拿华腾的交通卡系统做例子吧 先说数据结构:程序里面有很多用户信息,这些信息是用结构体存放,是用链表的形式,还是用哈希表等等的方法进行排列,这个就是数据结构 算法:要从这些数据结构里找出一个结点,是用遍历搜索呢还是用折半搜索之类的方法,叫做算法.LZ可以体会下.
金山屯区18439849732: 数据结构和算法是什么,要怎么学习数据结构和算法才能学的好 - ?
布岚产后: 基本: 线性表,链表,栈,队列 排序: 快速排序,堆排序,归并排序,希尔排序,插入排序,选择排序 二叉树: 前序,中序,后序遍历,层次遍历,包括递归算法和非递归算法两种 AVL树,Huffman编码 二叉树和树,森林之间的转换,穿线树 图算法: 深度优先遍历算法,广度优先遍历算法,最小生成树,最短路径 字符串: 查找子串,KMP算法等. 初学者一定要弄懂这些基本的算法.还有,要多动手练习书上的算法,代码是敲出来的.对于考试而言,多看看老师划的重点足矣.
金山屯区18439849732: 算法与数据结构区别 - ?
布岚产后: 举个例子,希望对你有帮助:你中午吃午饭,你的算法可能是酱紫: 1.夹菜 2.吃一口饭 3.如果吃饱,转4;如果没吃饱,转1 4.结束 而你选择的数据结构可能是酱紫: a)坐着吃 b)站着吃 c)躺着吃 如果你选择的是坐着吃的数据结构,那么你夹菜就是直着背夹菜,如果你选择站着吃得数据结构,你需要弯腰夹菜,但两种情况下都是进行夹菜的动作,以此类推.