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

[vainly]

[pfitseng]

时间，cpu够用
空间，内存够用

[canesten]

时间复杂度=算多久，1+1
空间复杂度=存多少，用个纸盒还是集装箱

[lcxseima]

时间复杂度：一次啪啪啪过程在时间的消费
空间复杂度：一次啪啪啪对宾馆大小的消费

[multiple1902]

至少上面这个绝对是错的......

[multiple1902]

是这样的，复杂度理论研究的绝对不是你「一次」啪啪啪产生的消耗啊。

[vainly]

@pfitseng @canesten @lcxseima @multiple1902
谢谢各位，
有这么一道题：有一串连续的数字（正负皆有），请在时间复杂度o(n),空间复杂度o(1)的情况下求出哪一段数字之和最大。

当初求值的时候，用了两个循环嵌套在一起，结果违背了空间复杂度o(1).

[multiple1902]

啊？你是怎么理解 O(1) 的空间复杂度的？我倒是觉得违背了时间复杂度 O(n)。

[tonyluj]

这不是 最大子序列和的问题吗？
数据结构与算法分析 C语言版 第一章就介绍了三种方法，两个循环嵌套是最慢的
算法导论里面也有介绍 分治法
leetcode也有这个题，看看别人做的

[jokester]

汉诺塔
用几个针做中转 >> 空间复杂度
用几步 >> 时间复杂度

[lijinma]

@vainly

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

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

使用动态规划；

代码：

<script src="https://gist.github.com/lijinma/2f8befa4f86b28665dc0.js"></script>

[MForever78]

@lijinma 这个空间复杂度是 O(n) 吧，其实只要用一个变量来存数组 a 就行了，读一个处理一个

[lijinma]

@MForever78

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

空间复杂度一般说的都是附加空间复杂度，我这里的附加空间，就是一个 sum，一个 result，明明就是 O(1)，你算空间复杂度还把 数组a也算上？？？？

[vainly]

@lijinma
@multiple1902 当初理解的一次函数调用即为时间o(1)
@MForever78
@tonyluj

非常感谢

[xieranmaya]

对于输入数据 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]

@xieranmaya 谢谢你。