美文网首页
算法复杂度

算法复杂度

作者: lichiii | 来源:发表于2018-07-22 22:45 被阅读0次

  算法复杂度分为时间复杂度和空间复杂度。一般对于某个算法来说,我们更关注它的性能,也即时间复杂度。本篇主要讲时间复杂度。

  《大话数据结构》里面对于算法时间复杂度的定义为:

  在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。

算法时间复杂度的表示与推导

  算法时间复杂度一般用O记法来表示。推导大O阶的过程如下:

  1.用常数1取代运行时间中的所有加法常数;

  2.在修改后的运行次数函数中,只保留最高阶项;

  3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。

  4.最终得到的结果就是大O阶。

  算法时间复杂度效率由高到低可排列为:

  O(1) > O(logn) > O(n) > O(nlogn) > O(n2) > O(n3) > O(2的n次方) > O(n!) > O(n的n次方)

  时间复杂度又分为最好情况、最坏情况、平均情况。

常见算法的时间复杂度(平均情况)分类

  常数阶O(1):数组中查找指定下标的值、hash表

  对数阶O(logn):二分法

  线性阶O(n):链表查找某个值

  O(nlogn):堆排序、快速排序、归并排序

  平方阶O(n2):直接插入排序、直接选择排序、冒泡排序

  O(n3) :暂无

  O(2的n次方) :暂无

  O(n!) :暂无

  O(n的n次方):暂无

相关文章

  • 算法相关

    算法复杂度相关概念:漫画:什么是时间复杂度?算法的时间复杂度和空间复杂度详解算法题库:力扣 一、排序算法 排序算法...

  • 算法基础知识

    算法的复杂度 算法的复杂度: 算法的时间复杂度和空间复杂度合称为算法的复杂度,一般不特别说明,讨论的时间复杂度均是...

  • 一位算法工程师的自我修养

    数据结构与算法 基本算法思想动态规划贪心算法回溯算法分治算法枚举算法 算法基础 时间复杂度 空间复杂度 最大复杂度...

  • 算法

    重拾算法:算法效率分析(一)(空间复杂度和时间复杂度) 详解算法的各种复杂度的差别有多大(带图) 算法复杂度 选择...

  • 算法复杂度

    算法的复杂度是以什么来度量的? 算法的复杂度是以时间复杂度和空间复杂度来计算的。 ①算法的时间复杂度 ...

  • 算法复杂度

    算法复杂度 算法复杂度的目的:分析代码执行的时间成本。我们从五个方面来介绍算法复杂度:时间复杂度、时间复杂度分类、...

  • 全网最好的数据结构学习文章合集系列之空间复杂度

    二、空间复杂度 算法概念 及 复杂度 简单的LRU Cache设计与实现 js算法初窥07(算法复杂度) 算法的时...

  • 数据结构-0-时间复杂度和空间复杂度

    1. 算法的复杂度: 算法的复杂度分为时间复杂度和空间复杂度。时间复杂度,是衡量算法执行时间的长度;空间复杂度,是...

  • 时间和空间复杂度

    算法复杂度 算法复杂度分为和。 时间复杂度是指执行算法所需要的计算工作量。 空间复杂度是指执行这个算法所需要的内存...

  • 算法的复杂度

    算法复杂度分为时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量,而空间复杂度是指执行这个算法所需要...

网友评论

      本文标题:算法复杂度

      本文链接:https://www.haomeiwen.com/subject/etvrmftx.html