数据结构
写在前面
1.1 数据结构
数据结构(DataStructure)是计算机存储、组织数据(增删改查)的⽅式,指相互之间存在⼀种或多种特定关系的数据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤,所以我们要学各式各样的数据结构,如:线性表、树、图、哈希等
1.2 算法
算法(Algorithm):就是定义良好的计算过程,他取⼀个或⼀组的值为输⼊,并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤,⽤来将输⼊数据转化成输出结果。
如何学好数据结构和算法: 秘诀是死磕代码,画图思考
算法的复杂度
算法在编写成可执⾏程序后,运⾏时需要耗费时间资源和空间(内存)资源。因此衡量⼀个算法的好坏,⼀般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。
时间复杂度主要衡量⼀个算法的运⾏快慢,⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。在计算机发展的早期,计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的迅速发展,计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。
时间复杂度
定义:在计算机科学中,算法的时间复杂度是⼀个函数式T(N),N指代变量,并不意味着只有N是变量,它定量描述了该算法的运⾏时间。时
间复杂度是衡量程序的时间效率,那么为什么不去计算程序的运⾏时间呢?
- 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系,⽐如同⼀个算法程序,⽤⼀个⽼编译器进⾏编译和新编译器编译,在同样机器下运⾏时间不同。
- 同⼀个算法程序,⽤⼀个⽼低配置机器和新⾼配置机器,运⾏时间也不同。
- 并且时间只能程序写好后测试,不能写程序前通过理论思想计算评估。
那么算法的时间复杂度是⼀个函数式T(N)到底是什么呢?这个T(N)函数式计算了程序的执⾏次数。通过c语⾔编译链接章节学习,我们知道算法程序被编译后⽣成⼆进制指令,程序运⾏,就是cpu执⾏这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N),假设每句指令执⾏时间基本⼀样(实际中有差别,但是微乎其微),那么执⾏次数和运⾏时间就是等⽐正相关,这样也脱离了具体的编译运⾏环境。执⾏次数就可以代表程序时间效率的优劣。⽐如解决⼀个问题的算 a程序T(N)=N,算法b程序T(N)=N^2,那么算法a的效率⼀定优于算法b。
要计算程序能代表增⻓量级的⼤概执⾏次数,复杂度的表⽰通常使⽤⼤O的渐进表⽰法。即用大O的渐进表示法表示时间复杂度。
空间复杂度
空间复杂度也是⼀个数学表达式,是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。
空间复杂度不是程序占⽤了多少bytes的空间,因为常规情况每个对象⼤⼩差异不会很⼤,所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似,也使⽤⼤O渐进表⽰法。
注意:函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定。
写在最后
最坏情况:任意输⼊规模的最⼤运⾏次数(上界)
平均情况:任意输⼊规模的期望运⾏次数
最好情况:任意输⼊规模的最⼩运⾏次数(下界)
⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界,也就是最坏运⾏情况。