大O复杂度表示法表示时间与空间复杂度

如何分析、统计算法的执行效率和资源消耗?能够粗略地估计算法的执行效率的方法,这就是时间、空间复杂度分析方法,大O复杂度表示法。

所属分类 数据

相关标签 算法复杂度分析

前言

我们通常检验代码的方式采用单元测试的形式,经过实际的代码运行来判断代码有无问题。

这种方式也可以统计运行效率(打印执行时间差),被称为过后统计法,存在以下以下问题:

  • 测试结果很是依赖测试环境(不同内存、内核的环境效率有所差异)
  • 测试结果受数据规模的影响很大(少量数据和大量数据所得到的结果往往不尽相同)

因此我们需要一种无需执行代码或具体测试的方式,能够粗略地估计算法的执行效率的方法。

评估一个方法(算法)的优劣,一般从以下维度:

  1. 正确性、可读性、健壮性(对不合理输入的反应能力和处理能力)
  2. 时间复杂度(time complexity):估算程序指令的执行次数(执行时间)
  3. 空间复杂度(space complexity):估算所需占用的存储空间

公式:T(n) = O(f(n))

  • n:表示数据规模的大小
  • T(n):表示代码执行的时间
  • f(n):表示每行代码执行的次数总和
  • O:表示代码的执行时间 T(n) 与 f(n) 表达式成正比

大O复杂度表示方法只是表示一种变化趋势。

当 n (基数)很大时,公式中的低阶、常量、系数三部分并不左右增加趋势,因此能够忽略。

时间复杂度

时间复杂度的全称是渐进时间复杂度(time complexity),表示算法的执行时间与数据规模之间的增长关系。

大O复杂度表示方法是一种估算方式,因此在进行估算时无需对全部代码进行阅读。

有三种形式和方式用于参考:

  1. 关注循环执行次数最多的一段代码

  2. 总复杂度等于量级最大的那段代码的复杂度

  3. 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

【】表示可能的执行次数

  • 常量阶 O(1):【13】并非执行一次,代码的执行时间不随 n 的增大而增长
  • 对数阶 O(logn):【3_log_2_n+25】
  • 线性阶 O(n):【8n+8】
  • 线性对数阶 O(nlogn):【6n+3n_log_3_n+90】
  • 指数阶 O(2^n) :【2^n】
  • 阶乘阶 O(n!):【1x2x3x...x(n-1)xn】
  • 平方阶 O(n^2) :【n^2+3n+3】
  • 立方阶 O(n^3) :【2n^3】
  • k次方阶 O(n^k) :【7n^k】

逐行代码列举。

// 假设每行代码执行时间 T
func cal(int n){
    int sum = 0 // 1T
    for i:=0;i<=n;i++ { // 1T + nT + nT
        sum = sum + i; // nT
    }
}
// 总执行时间 (3n+2)*T 
// 大O表示:T(n) = O(3n+2) 
// 忽略常量:T(n) = O(n)

前文提到,大O是一种估算,对于常量可以忽略。

func cal(int n){
    int sum = 0;// 忽略
    for i:=1;i<=n;i++ { // 关注循环次数
        for j:=1;j<=n;j++ { // 外循环 * 内循环 = n^2
            sum = sum + i*j // 忽略
        }
    }
}
// 大O表示:T(n) = O(n2)

多个循环取最大。

func cal(int n) {
    int sum := 0
    for i:=0; i < n; i++) {
        sum += i // O(n)
    }
    for j:=1; j< n {
        j = j * 3 // O(log-3-n) => O(logn)
    }
    for x:=1;x<=n;x++ { 
        for y:=1;y<=n;y++ {
            sum = sum + x*y // O(n^2)
        }
    }
}
// 大O表示:T(n) = O(n2) 取最大量级

空间复杂度

空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系。

空间复杂度的估算相比时间复杂度要简单,主需要关心申请内存的空间和次数。

因此,O(logn)、O(nlogn) 对数阶复杂度基本上用不到。

  • 常量阶 O(1):【13】
  • 线性阶 O(n):【8n+8】
  • 平方阶 O(n^2) :【n^2+3n+3】
  • k次方阶 O(n^k) :【7n^k】

米虫

做一个有理想的米虫,伪全栈程序猿,乐观主义者,坚信一切都是最好的安排!

本站由个人原创、收集或整理,如涉及侵权请联系删除

本站内容支持转发,希望贵方携带转载信息和原文链接

本站具有时效性,不提供有效、可用和准确等相关保证

本站不提供免费技术支持,暂不推荐您使用案例商业化

选择个人头像

昵称

邮箱

QQ

网址

评论提示

  • 头像:系统为您提供了12个头像自由选择,初次打开随机为你选择一个
  • 邮箱:可选提交邮箱,该信息不会外泄,或将上线管理员回复邮件通知
  • 网址:可选提交网址,评论区该地址将以外链的形式展示在您的昵称上
  • 记忆:浏览器将记忆您已选择或填写过得信息,下次评论无需重复输入
  • 审核:提供一个和谐友善的评论环境,本站所有评论需要经过人工审核