V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
way2explore2
V2EX  ›  编程

时间复杂度?这段代码的时间复杂度?

  •  
  •   way2explore2 · 178 天前 · 1017 次点击
    这是一个创建于 178 天前的主题,其中的信息可能已经有所发展或是发生改变。
    result = []
    for i in n:
      for jj in range(len(m)):
        if jj < 3:
          result.append((n,m))
        else:
          jj = len(m)
    

    n and m are two Python array.

    时间复杂度是多少呢?

    • O(n*m) 因为是嵌套循环
    • O(n) 因为 inner loop is fixed always 3
    • 其他?

    讨论一下?

    7 条回复    2021-06-04 10:40:30 +08:00
    kuangwinnie
        1
    kuangwinnie   178 天前
    ??这难道不是取决于你 m 是不是定值吗
    jhdxr
        2
    jhdxr   178 天前   ❤️ 1
    『 O(n) 因为 inner loop is fixed always 3 』是错的
    例如 m 的长度是 10,尽管你 result 只`append`了 3 次,但你的`jj=len(m)`会执行 7 次
    polaa
        3
    polaa   178 天前
    O(n*len(m))
    IgniteWhite
        4
    IgniteWhite   178 天前   ❤️ 1
    0
    因为两个空格缩进的 Python 跑不了
    rrfeng
        5
    rrfeng   178 天前
    @IgniteWhite 哈哈哈哈哈哈,启动解释器和读取文件的时间不算了吗
    delacey
        6
    delacey   178 天前
    @rrfeng 时间复杂度不计算常量部分
    way2explore2
        7
    way2explore2   178 天前   ❤️ 1
    @jhdxr 感謝慧眼識真,發現問題所在。

    哈哈
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3178 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 05:09 · PVG 13:09 · LAX 21:09 · JFK 00:09
    ♥ Do have faith in what you're doing.