目录
一 数据结构前言
1 数据结构
2 算法
3 算法与数据结构的关系
二 算法效率
1 算法效率：
2 复杂度
2.1 概念：
2.2分类：
2.3 空间复杂度在计算机高速发展的现代重要吗？
3 复杂度的重要性
三 时间复杂度
1定义：
2 间复杂度是衡量程序的时间效率所以要不要去计算程序的运⾏时间呢？
3 时间复杂度的计算方法（我们通过案例来讲解）
3.1 计算方法（⼤O的渐进表⽰法）
3.2通过时间复杂度计算得到的结果时确定的数吗？
3.3 案例
四 空间复杂度
1表示（计算）方法：
2 概念：
3案例
4常⻅复杂度对⽐
1定义：
一 数据结构前言
1 数据结构
2 算法：
3 算法与数据结构的关系
二 算法效率
1 算法效率：
因为现实中的问题有不同的解决办法，而每种方法的复制程度各不相同所对应的算法效率也不同，而我们编写代码是代码有其申请的空间和代码运行的时间，所以我们要从空间和运行时间两个角度分析算法效率，这时就要引入时间复杂度和空间复杂度。
2 复杂度
2.1 概念：
算法在编写成可执⾏程序后，运⾏时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好 坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
2.2分类：
时间复杂度：主要衡量⼀个算法的运⾏快
空间复杂度：主要衡量⼀个算法运⾏所需要的额外空间。
2.3 空间复杂度在计算机高速发展的现代重要吗？
3 复杂度的重要性
三 时间复杂度
1定义：
2 间复杂度是衡量程序的时间效率所以要不要去计算程序的运⾏时间呢？
1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。
3 时间复杂度的计算方法（我们通过案例来讲解）
3.1 计算方法（⼤O的渐进表⽰法）
⼤O符号（Big O notation）：是⽤于描述函数渐进⾏为的数学符号1. 时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时，低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。 【但是当有多个同等高次都保留或者要分类讨论】2. 如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。3. T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。
3.2通过时间复杂度计算得到的结果时确定的数吗？
3.3 案例
首先这个算法创建了变量flong，然后进行了N次循环，这N次循环中每次循环又嵌套了N次循环，循环过后又进行了2*N次循环，然后创建变量M，在进行M次循环。（M是一个确定的数）
据此我们可以得出本程序的基本操作次数（执行次数）T(N)=1+N^2+2*N+1+10
通过对N的取值分析，当N越来越大时，对结果影响最大的一项是N^2。通过⼤O的渐进表⽰法我们可知其时间复杂度时O(N^2)【根据时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时，低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。】
实际上我们计算复杂度时，也只是粗略的计算算法大概的执行次数，精确计算是很麻烦的因为不同的一个语句编译出的二进制指令是不同的而CPU处理数据时一秒可以处理上亿条指令所以是可以允许一些计算误差的。所以我们计算算法的时间复杂度时，只需要计算程序的大概执行次数就可以了，保留最高次即可（但是当有多个同等高次都保留）。
案例二
分析：这个算法进行了2*N次循环，又进行了M次循环，还进行了两次变量创建，一次打印。T(N)=1+2*N+1+M+1
忽略掉可忽略项 T(N)=2*N+M (M=10)
又因为M是已知的。
所以根据大O的渐进表示法可得本算法的时间复杂O（N）。（注意不是O（2*N））【根据如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数 对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。 】
案例三
分析：本算法根据大O的渐近表示法可得时间复杂度为O(M+N)，因为M和N时同等高次所以需要分类讨论：
1.M>>N时———O(M)
2.M<<N时——O(N）
3.M和N差不多时—O(M）或O(N)【根据有多个同等高次都保留或者要分类讨论】
分析：本算法的执行次数为T(N)=100;
根据大O的渐近表示法可的本算法的时间复杂度为O(1).【根据T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。】
案例五【多种情况：最好\最坏\中间】
分析：该算法的执行次数不是一个固定的值，而是需要根据实际的情况来确定，如果要查找的字符出现在字符串的前端，执行次数相对就少。反之，如果要查找的字符串出现在字符串的后端，执行的系数就会较多。
如果要查找的字符出现在字符串的第一个位置（字符串的前端），T(N)=1.
如果要查找的字符出现在字符串的最后位置（字符串的后端），T(N)=N.
如果要查找的字符出现在字符串的中间，T(N)=N/2.(N为字符串的长度)
因此，本算法的时间复杂度分为：
最好情况：O(1)
中间情况：O(N)
最坏情况：O(N)
这里我们都是取最坏情况因为我们每个人都不能保证我们自己的算法是最优
案例六·
注意因为在计算机中底数很难表示再加上当n接近⽆穷⼤时，底数的⼤⼩对结果影响不⼤。因此，⼀般情况下不管底数是多少都可以省略不写。所以我们在课件中和书籍中可以用 log2 n 、 log n 、 lg n 的表⽰不同书籍的表⽰⽅式不同，以上写法差别不⼤，我们建议使⽤ log n
案例七（递归）
分析：调⽤⼀次Fac函数的时间复杂度为 O(1)⽽在Fac函数中，存在n次递归调⽤Fac函数 因此：阶乘递归的时间复杂度为： O(n)
总结：递归的时间复杂度=单次递归的时间复杂度*递归次数。
案例八（冒泡排序）
分析：因为数组的情况不同对应的时间复杂度也不同所以要分类讨论
1若数组有序，则： T ( N ) = N2若数组有序且为降序，则： T ( N ) =2 / N ∗ ( N + 1)3若要查找的字符在字符串中间位 置，则：为（1+2 ）/2因此：冒泡排序的时间复杂度取最差情况为： O ( N 2 )
四 空间复杂度
1表示（计算）方法：
也是大O渐近表示法【所以空间复杂度也是一个表达式】
2 概念：
3案例
分析：函数栈帧在编译期间已经确定好了，只需要关注函数在运⾏时额外申请的空间BubbleSort额外申请的空间有exchange等有限个局部变量，使⽤了常数个额外空间（没有大量申请空间 ）因此空间复杂度为 O(1)
案例二
分析：Fac函数递归调⽤了N次，额外开辟了N个函数栈帧，每个栈帧使⽤了常数个空间因此空间复杂度为： O(N)
总结：递归的空间复杂度=单次递归的空间复杂度*递归次数。
4常⻅复杂度对⽐
本篇文章就到此结束，欢迎大家订阅我的专栏，欢迎大家指正，希望有所能帮到读者更好了算法与数据结构相关知识 ，觉得有帮助的还请三联支持一下~后续会不断更新C/C++相关知识，我们下期再见。
