文章目录1.数据结构1.1 数据结构分类1.1.1 逻辑结构分类1.1.2 物理结构分类2.算法3.什么是复杂度3.1 时间复杂度的计算3.2时间复杂度举例3.3空间复杂度1.数据结构数据结构是指用来组织和存储数据的集合1.1 数据结构分类我们可以把数据结构分为逻辑结构和物理结构两大类1.1.1 逻辑结构分类逻辑结构是从具体问题中抽象出来的模型是抽象意义上的结构按照对象中数据元素之间的相互关系分类。a.集合结构集合结构中数据元素除了属于同一个集合外他们之间没有任何其他的关系b.线性结构线性结构中的数据元素之间存在一对一的关系c.树形结构树形结构中的数据元素之间存在一对多的层次关系d.图形结构图形结构的数据元素是多对多的关系1.1.2 物理结构分类逻辑结构在计算机中真正的表示方式又称为映像称为物理结构也可以叫做存储结构。常见的物理结构有顺序存储结构、链式存储结构。1顺序存储结构把数据元素放到地址连续的存储单元里面其数据间的逻辑关系和物理关系是一致的比如我们常用的数组就是顺序存储结构。顺序存储结构存在一定的弊端就像生活中排时也会有人插队也可能有人有特殊情况突然离开这时候整个结构都处于变化中此时就需要链式存储结构。2链式存储结构是把数据元素存放在任意的存储单元里面这组存储单元可以是连续的也可以是不连续的。此时数据元素之间并不能反映元素间的逻辑关系因此在链式存储结构中引进了一个指针存放数据元素的地址这样通过地址就可以找到相关联数据元素的位置2.算法1算法是根据一定的条件对一些数据进行计算得到需要的结果。2在程序中我们也可以用不同的算法解决相同的问题而不同的算法的成本也是不相同的。总体上一个优秀的算法追求以下两个目标①花最少的时间完成需求②占用最少的内存空间完成需求3.什么是复杂度1时间复杂度是指执行算法所需要的计算工作量。①一个算法中的语句执行次数称为语句频度或时间频度表示为T(n)O(f(n)),n表示问题的规模。它表示随着问题规模n的增大算法执行时间的增长率和f(n)的增长率相同称作算法的渐近时间复杂度简称时间复杂度其中f(n)是问题规模n的某个函数时间复杂度就是时间频度去掉低阶项和首项常数。在这里我们需要明确一个事情执行次数执行时间②最坏情况下的时间复杂度称为最坏时间复杂度。一般不特别说明讨论的时间复杂度均是最坏情况下的时间复杂度。③在最坏情况下的时间复杂度为T(n)O(n)它表示对于任何输入实例该算法的运行时间不可能大于O(n)2空间复杂度是指执行这个算法所需要的内存空间3.1 时间复杂度的计算1找出算法中的基本语句算法中执行次数最多的那条语句就是基本语句通常是最内层循环的循环体2计算基本语句的执行次数的数量级①只需计算基本语句执行次数的数量级这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可②可以忽略所有最低次幂和最高次幂的系数。这样能够简化算法分析并且使注意力集中在最重要的一点上即增长率3用大O记号表示算法的时间性能将基本语句执行次数的数量级放入大O记号中3.2时间复杂度举例1一个简单语句的时间复杂度为O(1)intcount0;2100个简单语句的时间复杂度也为O(1)因为100是常数不是趋向无穷大的n 3一个循环的时间复杂度为O(n)intn8;count0;for(inti1;in;i)count;(4)时间复杂度为O(log2n)的循环语句intn8,count0for(inti1;in;i*2)count;(5)时间复杂度为O(n²)的二重循环体intn8;count0;for(inti1;in;i)for(intj1;jn;j)count;(6)时间复杂度为O(nlog2n)的二重循环体intn8;count0;for(inti1;in;i*2)for(intj1;jn;j)count;3.3空间复杂度1算法的存储量包括①程序本身所占空间②输入数据所占空间③辅助变量所占空间2输入数据所占空间只取绝于问题本身和算法无关则只需要分析除输入和程序之外的辅助变量所占额外空间3空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度一般也作为问题规模n的函数以数量级形式给出记作S(n)O(g(n))(4)例子①例子①intfun(intn){inti,j,k,s;s0;for(i0;in;i)for(j0;ji;j)for(k0;kj;k)s;return(s);}分析i,j,k,s各占一个空间总共4个空间即S(n)O(1)例子②(递归)voidfun(inta[],intn;intk)// 数组a共有n个元素{inti;if(kn-1)for(i0;in;i)printf(%d\n,a[i]);//执行n次else{for(ik;in;i)a[i]a[i]i*i;//执行n-k次**fun(a,n,k1);**}}此属于递归算法每次调用本身都要分配空间fun(a,n,0)的空间复杂度为O(n)