这是一个创建于 3786 天前的主题，其中的信息可能已经有所发展或是发生改变。
 |
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 谢谢你。
|
Select Language