这得分两层来理解。

我们生活中处处存在数据#xff0c;什么抖音热点上的国际大事#xff0c;什么懂的都懂的雍正卸甲等等一系列我们用户看得到的什么抖音热点上的国际大事什么懂的都懂的雍正卸甲等等一系列我们用户看得到的就是抖音存储在后台服务器的数据。

但这些数据都有一个特点那就是都在抖音的热搜榜单上而这个榜单就是结构保证数据在一个固定的位置里以便用户浏览。

此外有了数据结构就离不开算法。

那么我们刚刚说了数据结构是把数据有规律的存储在一个结构中那么怎么从结构中有效率的存取数据这就是算法。

时间复杂度

有了算法就存在时间复杂度和空间复杂度。

因为计算机现在的内存越来越大所以时间复杂度比空间复杂度更显得重要。

所以我们先来了解时间复杂度

时间复杂度最重要的词就是时间这里的时间就是指一个程序运行时的时间如果时间复杂度越少那么证明这个算法越好。

时间复杂度计算用函数式T(N)表示

那为什么我们不提前算出这个程序的时间复杂度来写出最优解的代码呢这里就涉及到计算机的问题。

因为程序运⾏时间和编译环境和运⾏机器的配置都有关系⽐如同⼀个算法程序⽤⼀个⽼编译

器进⾏编译和新编译器编译在同样机器下运⾏时间不同。

同⼀个算法程序⽤⼀个⽼低配置机器和新⾼配置机器运⾏时间也不同。

并且时间只能程序写好后测试不能写程序前通过理论思想计算评估。

下面我们来看一段代码:

这里我们就太小看我们的计算机了我们计算机一秒钟cpu可以执行上亿次这小小的一次当然可以忽略不计。

所以说我们计算的时间复杂度并不准确只是粗略估计而已这时候我们就用一个新的符号表示.

⼤O符号Big

notation是⽤于描述函数渐进⾏为的数学符号;这里用来表示估算的时间复杂度。

那么这里还是跟T(N)一样算吗如果是这样我们就没必要用另外一个符号来表示了。

这里就涉及到算O的规则:

时间复杂度函数式T(N)中只保留最⾼阶项去掉那些低阶项因为当N不断变⼤时低阶项对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了。

如果最⾼阶项存在且不是1则去除这个项⽬的常数系数因为当N不断变⼤这个系数对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了T(N)中如果没有N相关的项⽬只有常数项⽤常数1取代所有加法常数。

10,这里的最高阶是N2所以去掉其他的低阶复杂度就为(ON^2)

小试牛刀

}这里的T(N)MN那我们再来算O(N),这里M和N都是同阶所以不符合第一条规则也没有对应第二条和第三条所以为o(NM)那么有人就问了万一N比M大呢是不是因该是O(N).这里问题就是你怎么知道N比M大万一是M比N大呢所以保险起见我们都留下来。

const

}这里我们是查找character在str中的位置这里我补充一个知识点:

1.最好情况

}最坏情况下又因为保留高阶去掉n/2(第一条),忽略系数(第二条)所以为ON^2

void

空间复杂度要注意的是他的计算表示也是用O来表示并且他的规则与时间复杂度一样遵守那三条规则

函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定

例1: