数据结构
数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。
为什么要学习数据结构?
学习数据结构学习的是逻辑思维和抽象思维的能力。程序设计=数据结构+算法,底层和源码的开发更是离不开数据结构。想要学的更深入就要学习数据结构。
什么是数据结构?
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的逻辑结构与物理结构
数据结构的逻辑结构是指数据元素之间的相互关系,逻辑结构分为以下四种:
集合结构:集合中的数据结构除了同属于一个集合外,它们之间没有其他关系线性结构:线性结构中的数据元素之间是一对一的关系树形结构:树形结构中的数据元素之间存在一种一对多的层次关系图形结构:图形结构的数据元素是多对多的-关系数据结构的物理结构是指逻辑结构在计算机中的存储形式
顺序存储结构;开辟一组连续的空间存储数据,通常用数组来实现,数组中空间本身是连续的,保证了数据之间的关系链式存储结构:开辟一组随机的空间存储数据,通常用节点来实现,节点不仅要存储数据,还要存储 下一节点的位置以保证数据之间的关系我们要根据应用场景的不同灵活选择最合适的数据结构
算法
算法是解决特定问题求解的描述,在计算机中指令的有序序列,并且每条指令表示一个或多个操作,就是求解一个问题的步骤。
怎么评价一个算法的好坏?
事后统计方法:通过设计好的程序和数据,利用计算机计时器对不同算法程序的运行时间进行比较,从而确定算法效率的高低
事前分析估算法:在计算机程序编制前,依据统计方法对算法进行估算,一个程序在计算机上运行时所消耗的时间取决下列因素:
算法采用的策略和方法编译产生的代码质量问题的输入规模机器执行指令的执行速度时间复杂度
时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。
在进行算法时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随 n 的变化情况并确定T(n)的数量级,算法时间复杂度,也就是时间度量,记作:T(n)= O(f(n))。
它表示随问题规模 n 的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度。
其中f(n)是问题规模n的某个函数。
T(n)是具体的次数,O(n)不是具体的执行数,看增长率。
常见的几个时间复杂度
常数阶O(1) 没有循环对数阶O(logn) 有循环,加速度减小的加速运动线性阶O(n) 循环情况nlogn阶 O(nlog n) 二叉树里用平方阶O(n^2)立方阶O(n^3)指数阶O(2^n)时间复杂度从上到下增大
我们考虑的时间复杂度都是最坏情况