1
pfitseng 2014-07-17 11:27:09 +08:00
时间,cpu够用
空间,内存够用 |
2
canesten 2014-07-17 11:30:08 +08:00
时间复杂度=算多久,1+1
空间复杂度=存多少,用个纸盒还是集装箱 |
3
lcxseima 2014-07-17 11:40:45 +08:00
时间复杂度:一次啪啪啪过程在时间的消费
空间复杂度:一次啪啪啪对宾馆大小的消费 |
4
multiple1902 2014-07-17 11:41:58 +08:00 via Android 1
至少上面这个绝对是错的......
|
5
multiple1902 2014-07-17 11:42:42 +08:00 via Android
是这样的,复杂度理论研究的绝对不是你「一次」啪啪啪产生的消耗啊。
|
6
vainly OP @pfitseng @canesten @lcxseima @multiple1902
谢谢各位, 有这么一道题:有一串连续的数字(正负皆有),请在时间复杂度o(n),空间复杂度o(1)的情况下求出哪一段数字之和最大。 当初求值的时候,用了两个循环嵌套在一起,结果违背了空间复杂度o(1). |
7
multiple1902 2014-07-17 12:22:59 +08:00
啊?你是怎么理解 O(1) 的空间复杂度的?我倒是觉得违背了时间复杂度 O(n)。
|
8
tonyluj 2014-07-17 12:35:05 +08:00 1
这不是 最大子序列和的问题吗?
数据结构与算法分析 C语言版 第一章就介绍了三种方法,两个循环嵌套是最慢的 算法导论里面也有介绍 分治法 leetcode也有这个题,看看别人做的 |
9
jokester 2014-07-17 13:47:52 +08:00 1
汉诺塔
用几个针做中转 >> 空间复杂度 用几步 >> 时间复杂度 |
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> |
11
MForever78 2014-07-17 14:35:19 +08:00
@lijinma 这个空间复杂度是 O(n) 吧,其实只要用一个变量来存数组 a 就行了,读一个处理一个
|
12
lijinma 2014-07-17 14:38:11 +08:00 1
@MForever78
你哪看到我的空间复杂度是O(n)了? 空间复杂度一般说的都是附加空间复杂度,我这里的附加空间,就是一个 sum,一个 result,明明就是 O(1),你算空间复杂度还把 数组a也算上???? |
13
vainly OP |
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 这种做法还是有些不严谨的,但在多数情况下是可以适用的。 如果有纰漏还请大神指正 |
15
vainly OP @xieranmaya 谢谢你。
|