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

能不能用简介易懂的语言解释时间复杂度和空间复杂度?

  •  
  •   vainly · 2014-07-17 11:14:12 +08:00 · 5900 次点击
    这是一个创建于 3781 天前的主题,其中的信息可能已经有所发展或是发生改变。
    15 条回复    2015-08-19 12:48:05 +08:00
    pfitseng
        1
    pfitseng  
       2014-07-17 11:27:09 +08:00
    时间,cpu够用
    空间,内存够用
    canesten
        2
    canesten  
       2014-07-17 11:30:08 +08:00
    时间复杂度=算多久,1+1
    空间复杂度=存多少,用个纸盒还是集装箱
    lcxseima
        3
    lcxseima  
       2014-07-17 11:40:45 +08:00
    时间复杂度:一次啪啪啪过程在时间的消费
    空间复杂度:一次啪啪啪对宾馆大小的消费
    multiple1902
        4
    multiple1902  
       2014-07-17 11:41:58 +08:00 via Android   ❤️ 1
    至少上面这个绝对是错的......
    multiple1902
        5
    multiple1902  
       2014-07-17 11:42:42 +08:00 via Android
    是这样的,复杂度理论研究的绝对不是你「一次」啪啪啪产生的消耗啊。
    vainly
        6
    vainly  
    OP
       2014-07-17 12:21:22 +08:00
    @pfitseng @canesten @lcxseima @multiple1902
    谢谢各位,
    有这么一道题:有一串连续的数字(正负皆有),请在时间复杂度o(n),空间复杂度o(1)的情况下求出哪一段数字之和最大。

    当初求值的时候,用了两个循环嵌套在一起,结果违背了空间复杂度o(1).
    multiple1902
        7
    multiple1902  
       2014-07-17 12:22:59 +08:00
    啊?你是怎么理解 O(1) 的空间复杂度的?我倒是觉得违背了时间复杂度 O(n)。
    tonyluj
        8
    tonyluj  
       2014-07-17 12:35:05 +08:00   ❤️ 1
    这不是 最大子序列和的问题吗?
    数据结构与算法分析 C语言版 第一章就介绍了三种方法,两个循环嵌套是最慢的
    算法导论里面也有介绍 分治法
    leetcode也有这个题,看看别人做的
    jokester
        9
    jokester  
       2014-07-17 13:47:52 +08:00   ❤️ 1
    汉诺塔
    用几个针做中转 >> 空间复杂度
    用几步 >> 时间复杂度
    lijinma
        10
    lijinma  
       2014-07-17 14:19:50 +08:00   ❤️ 2
    @vainly

    你用了两个循环,明显时间复杂度是 O(n平方)了;

    使用楼上 @tonyluj 的方法,求最大子序列和;

    使用动态规划;

    代码:

    <script src="https://gist.github.com/lijinma/2f8befa4f86b28665dc0.js"></script>
    MForever78
        11
    MForever78  
       2014-07-17 14:35:19 +08:00
    @lijinma 这个空间复杂度是 O(n) 吧,其实只要用一个变量来存数组 a 就行了,读一个处理一个
    lijinma
        12
    lijinma  
       2014-07-17 14:38:11 +08:00   ❤️ 1
    @MForever78

    你哪看到我的空间复杂度是O(n)了?

    空间复杂度一般说的都是附加空间复杂度,我这里的附加空间,就是一个 sum,一个 result,明明就是 O(1),你算空间复杂度还把 数组a也算上????
    vainly
        13
    vainly  
    OP
       2014-07-17 15:30:28 +08:00
    @lijinma
    @multiple1902 当初理解的一次函数调用即为时间o(1)
    @MForever78
    @tonyluj

    非常感谢
    xieranmaya
        14
    xieranmaya  
       2015-08-19 11:32:56 +08:00
    对于输入数据 n
    你循环的次数写成 n 的表达式,就是时间复杂度
    你申请的变量数量写成 n 的表达式,就是空间复杂度

    例如计算 1 到 n 的和,输入为 n
    如果你用循环来计算,那么循环次数是 n 次,于是时间复杂度为 O (n )。
    不管 n 是多大,变量最多也就不超过 5 个,于是空间复杂度为 O (5 ),也就是 O (1 ),常数全变成 1 就对了

    如果你用前 n 项和的公式来计算,只要一次计算即可: n*(n+1 )/2 ,并没有循环,于是时间复杂度为 O (3 )[此处进行了三次计算:+,*,/],常数变为 1 就是 O (1 ),变量数量这里可能只需要两个,于是空间复杂度也为 O (1 )

    常数直接变为 1 这种做法还是有些不严谨的,但在多数情况下是可以适用的。
    如果有纰漏还请大神指正
    vainly
        15
    vainly  
    OP
       2015-08-19 12:48:05 +08:00
    @xieranmaya 谢谢你。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1284 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 17:43 · PVG 01:43 · LAX 09:43 · JFK 12:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.