首页 > 其他分享 >大O表示法

大O表示法

时间:2024-01-14 17:48:35浏览次数:25  
标签:复杂度 Hello 表示法 print 2n 代码 第二组

目录

时间复杂度

  • 执行次数函数大O表示
    13O(1)常数阶
    2n+3O(n)线性阶
    3n²+2n+1O(n2)平方阶
    5log2n+20O(logn)对数阶
    2n+3nlog2n+19O(nlogn)nlogn阶
    6n3+2n2+3n+4O(n3)立方阶
    2nO(2n)指数阶
  • # 第一组
    print('Hello,World')
    print('Hello,Python')
    print('Hello,Java')
    ​
    # 第二组
    for i in range(n):
        print('Hello,World')
        for j in range(n):
            print('Hello,World')
    

    在第一组代码中,有三行代码,共执行了3次,所以它的运行时间为O(3×t);
    第二组代码中,第一个for循环中执行了print,所以执行时间为n×t,在嵌套的for循环中,执行了n次,所以运行时间为n²×t,所以第二组代码运行时间为O((n+n²)×t)。

空间复杂度

  • 空间复杂度是用来评估算法内存占用大小的式子。空间复杂度的表示方式与时间复杂度完全一样。示例代码如下:

    # 第一组
    a='11'                  #变量
    b='22'
    c='33'
    ​
    # 第二组
    a=[1,2,3,,...,n]            # 一维数组
    ​
    # 第三组
    a[m][n]=9               # 二维数组
    

    在第一组代码中,有a、b、c三个变量,所以其空间复杂度为O(1);

    第二组代码中,a是一维数组,长度为n,所以其空间复杂度为O(n);

    第三组代码中,a是二维数组,长度mn,所以其空间复杂度为O(mn);

    注意:一般情况下,时间复杂度的优先级比空间复杂度优先级高,也就是优先选择时间复杂度低的算法。

标签:复杂度,Hello,表示法,print,2n,代码,第二组
From: https://www.cnblogs.com/ComputerTech/p/17963890

相关文章

  • 离散数学 第一章 命题逻辑 1-1 命题及其表示法
    在数理逻辑中,为了表达概念,陈述理论和规则,常常需要应用语言进行描述,但是日常使用的自然语言进行描述,往往叙述时不够确切,也易产生二义性,因此就需要引入一种目标语言,这种目标语言和一些公式符号,就形成了数理逻辑的形式符号体系。所谓目标语言就是表达判断的一些语言的汇集,而判断就是对......
  • 最小表示法学习笔记
    找出与\(S\)循环同构的字符串中字典序最小的那一个。记录两个指针\(i\)和\(j\),表示当前可能成为答案的最前面两个位置。初值为字符串的前两个位置\(1\)和\(2\)。每次按\(k\)从小到大暴力比较\(S_{i+k}\)和\(S_{j+k}\)的大小,当遇到\(S_{i+k}>S_{j+k}\)时,\(i\simi......
  • 浮点表示法
    小数的二进制表示法,即浮点数,IEEE754浮点数如何在计算机中储存,即符号位,指数位,小数位(通常翻译做尾数)取值范围取决于指数位,计算精度取决于小数位(尾数)。小数位越多(比如双精度是52位),则能表示的数越大,那么计算精度则越高。单精度的小数位在计算机中只有23位(二进制),换算到十进制只能......
  • 补码表示法
    所谓的补码表示法,它是有符号整数最常用的二进制表示法。对正数求反码(即对每个位进行NOT运算),然后加1,舍弃MSB的任何进位,就可以得到这个数字的负数。表示+1的0001的反码是1110,加1就可以得到表示–1的1111。同理,+2是0010,它的反码是1101,再加1就可以得到表示–2的1110。......
  • 算术表达式求值法(表达式求值)之后序表示法求值
    概念后序表示法(PostfixNotation)又称为逆波兰表示法(ReversePolishNotation,RPN),是一种用于表示数学表达式的方法,其中运算符位于它们的操作数之后。这种表示法非常适合用栈来计算表达式的值,因为它消除了括号的需求,使计算机能够轻松地理解和求解表达式。例如,表达式"3+4"在后......
  • 算术表达式求值法(表达式求值)之前序表示法求值
    概念前序表示法,也称为前缀表示法或波兰表示法(Polishnotation),是一种用于表示数学表达式和算术运算的方法。这种表示法的特点是将运算符置于操作数之前,而不是像传统的中缀表示法(例如,2+3)将运算符置于操作数之间。前序表示法具有一些优点,尤其在计算机科学和计算器设计中非常有用。......
  • 算术表达式的表示法(即求值法)
    说明算术表达式的表示法有多种,其中最常见的包括中缀表达法、前缀表达法和后缀表达法。这些表示法用于表示和求解数学表达式,它们在计算机科学和数学领域都有广泛的应用。中缀表达法、前缀表达法和后缀表达法是操作符的位置来分类的。操作符位于2个操作之间叫中缀表达法,操作符位于......
  • 【有符号数】原码,反码,补码表示法
     1.原码......
  • 英语“方位”表示法
      英语“方位”表示法作者:未知 发布会员:wjw 版权:转载 添加时间:2007-6-6 阅读:1054次【字体:大中小】     英语方位表示法为数不少,但容易混淆。特别是几个介词的用法常常令自学者无所适从。有时“一字之差”就可能 “失之千里”。为此......
  • 最小表示法学习笔记
    定义一个字符串\(S\)的最小表示法为该字符串所有循环同构字符串中字典序最小的一个。比如:\(abca\),对于他,循环同构字符串就有\(aabc\),\(caab\),\(bcaa\),其中字典序最小的是\(aabc\)。那么我们说\(aabc\)就是\(abca\)最小表示法。算法流程介绍考虑对于一对子串\(A,B\),......