锐客网

  1. 首页 > it技术 > >

算法|【算法】时间复杂度真的不“复杂”

算法时间复杂度


文章目录

      • 算法的时间复杂度
      • 常见的时间复杂度
      • 平均时间复杂度、最坏时间复杂度、空间复杂度

写一篇关于时间复杂度的文章，这一定是入门算法必备的知识点了！
作者也是一边学习一边分享，如果觉得写的还不错的话，欢迎点一个?收藏?再走哦~~~
算法|【算法】时间复杂度真的不“复杂”
文章图片

算法的时间复杂度
作用：通过分析算法时间复杂度来判断哪个程序更优秀。
这里给大家列出数学上的解释：
时间频度（T（n））：语句执行的次数。
假定辅助函数f(n)，当n趋近于无穷大时，T(n)/f(n)的极限为不为零的常数时，则记作T(n)=O(f(n))。
O(f(n))则是时间复杂度。
其实这里看不懂也没有关系，并不影响我们去计算时间复杂度。
【算法|【算法】时间复杂度真的不“复杂”】忽略（极限思想）：在计算时间复杂度时，经常会忽略一些对于算法整体的时间复杂度影响不大的项。例如：常数项、低次项、系数。
所以在计算时间复杂度时，一般要进行三步:
  1. 加法常数可忽略。
  2. 只保留最高阶项。
  3. 去除最高阶项的系数。
常见的时间复杂度
  • 算法时间复杂度从小到大依次为（附带举例）：
  1. 常数阶O(1)：没有循环结构等复杂结构。
  2. 对数阶O(log2n)：
int i=1; while(i

  1. 线性阶O(n)：一层for循环。
  2. 线性对数阶O(nlog2n)：一层for循环内嵌套了对数阶的循环。
  3. 平方、立方O(n^2),O(n^3)：双重for循环、多重for循环。
  4. 指数阶O(2^n) 和阶乘O(n!)：在实际运用中应避免使用指数阶/阶乘时间复杂度的算法。
算法|【算法】时间复杂度真的不“复杂”
文章图片

平均时间复杂度、最坏时间复杂度、空间复杂度
  • 平均时间复杂度
    平均时间复杂度是指所有可能的输入实例等概率出现的情况下，算法的运行时间。
  • 最坏时间复杂度
    在讨论时间复杂度时，均指最坏情况下的时间复杂度。保证了算法的运行时间不会超过最坏时间复杂度。
  • 空间复杂度
    作用：度量算法在运行过程中临时占用存储空间的大小。
    在算法分析时，主要讨论时间复杂度，一些缓存产品和算法（基数排序）本质就是用空间换时间

    推荐阅读


    上一篇：数据结构|数据结构与算法—— 树

    下一篇：计算机视觉算法工程师|算法工程师15——数据结构与算法加强版