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

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

  •  
  •   way2explore2 · 2021-06-04 05:30:04 +08:00 · 1191 次点击
    这是一个创建于 388 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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  
       2021-06-04 06:22:29 +08:00
    ??这难道不是取决于你 m 是不是定值吗
    jhdxr
        2
    jhdxr  
       2021-06-04 07:37:39 +08:00   ❤️ 1
    『 O(n) 因为 inner loop is fixed always 3 』是错的
    例如 m 的长度是 10,尽管你 result 只`append`了 3 次,但你的`jj=len(m)`会执行 7 次
    polaa
        3
    polaa  
       2021-06-04 09:09:22 +08:00
    O(n*len(m))
    IgniteWhite
        4
    IgniteWhite  
       2021-06-04 09:39:29 +08:00   ❤️ 1
    0
    因为两个空格缩进的 Python 跑不了
    rrfeng
        5
    rrfeng  
       2021-06-04 10:05:39 +08:00
    @IgniteWhite 哈哈哈哈哈哈,启动解释器和读取文件的时间不算了吗
    delacey
        6
    delacey  
       2021-06-04 10:36:12 +08:00
    @rrfeng 时间复杂度不计算常量部分
    way2explore2
        7
    way2explore2  
    OP
       2021-06-04 10:40:30 +08:00   ❤️ 1
    @jhdxr 感謝慧眼識真,發現問題所在。

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