算法与数据结构——复杂度

目录

一  数据结构前言

             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.2通过时间复杂度计算得到的结果时确定的数吗？

3.3   案例

分析：本算法的执行次数为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 ) = N

2若数组有序且为降序，则： 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++相关知识，我们下期再见。