算法复杂度分析

蔚落 2022-11-14 10:19 275阅读 0赞

复杂度分析

文章目录

  • 复杂度分析
    • 一、时间复杂度
    • 二、空间复杂度

一、时间复杂度

  1. 计算时间复杂度的方法：

只保留去掉系数的最高阶项，且一般讨论的都是最坏情况下的复杂度，如：

T(n) = 2n2 + 7n + 1 => O(n2)

  1. 常见的时间复杂度及排序：

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(nk) < O(2n) < O(n!)

  1. 常见的时间复杂度分析：

① 常数阶：O(1)

只要代码中没有循环结构(仅有赋值，比较等)，无论代码多长，时间复杂度总为常数阶

② 对数阶：O(logn)

  1. while(i < n) { 
  2.     i = i * 2; //时间复杂度为O(log2n)
  3. }
  5. while(i < n) { 
  6.     i = i * 3; //时间复杂度为O(log3n)
  7. }

③ 线性阶：O(n)

  1. for (int i = 0; i < n; i++) { 
  2. //常数复杂度的操作
  3. }

④ 线性对数阶：O(nlogn)

  1. for (int i = 0; i < n; i++) { 
  2.     while (i < n) { 
  3.         i = i * 2; 
  4.     }
  5. }

⑤ 平方阶：O(n2)

  1. for (int i = 0; i < n; i++) { 
  2.     for (int j = 0; j < n ; j++) { 
  3.         //常数复杂度的操作
  4.     }
  5. }
  6. //持续嵌套for循环可形成三次方、四次方...

​

  1. 时间复杂度的注意事项：

(1) 并列的循环复杂度不叠加

(2) 嵌套的循环复杂度叠加

二、空间复杂度

指的是在原数据结构的基础上为完成某一操作而额外申请的空间

常见的空间复杂度有：O(1)，O(n)

注意：常数的空间复杂度都当作O(1)

发表评论

表情：
评论列表 （有 0 条评论，275人围观）

还没有评论，来说两句吧...

相关阅读

    相关 算法复杂度分析

    时间复杂度计算 时间复杂度的全称是渐进时间复杂度，用来评估算法执行效率与数据规模增长的变化趋势，目的是避免数据规模过大时导致系统挂掉的情况。 以单行为一个unt\_ti

    傷城~傷城~/ 0 赞/ 183 阅读

    相关 算法复杂度分析

    复杂度分析 文章目录 复杂度分析 一、时间复杂度 二、空间复杂度 一、时间复杂度 1. 计算时间复杂度的方法： 只保留去

    蔚落蔚落/ 0 赞/ 276 阅读

    相关 算法分析之复杂度

    复杂度分为两大部分：时间复杂度和空间复杂度 时间复杂度：是度量算法执行的时间长短或者说是程序执行的次数。 详细说明： 一个算法，处理n条数据需要的时间可以用表达

    妖狐艹你老母妖狐艹你老母/ 0 赞/ 307 阅读

    相关 算法的复杂度分析

    复杂度分析是什么 代码的复杂度分为时间复杂度与空间复杂度。 数据结构与算法解决的核心问题就是让代码更“快”、更“省”。具体来说，就是执行的时间尽可能的短，占用的空间尽可

    我不是女神ヾ我不是女神ヾ/ 0 赞/ 346 阅读

    相关 算法复杂度分析

    采用不同的算法，会有不同的效率。因此，知道某个算法的运行速度和占用的内存空间，对于选择正确的算法来解决问题非常有帮助。 3.1 时间复杂度 算法的时间复杂度是指算法需要

    ╰+攻爆jí腚メ╰+攻爆jí腚メ/ 0 赞/ 390 阅读