问道careercup 150 题目的复杂度 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问道careercup 150 题目的复杂度

问道careercup 150 题目的复杂度# JobHunting - 待字闺中

j*s2013-03-08 08:03

1 楼

9.10 n boxs, height,width,depth, find the max height.
Solution,
Sub-problem, find the max depth that is using box b_i as bottom. Using
recursion + cache.
请问各位大神算法的复杂度是多少，怎么得出来的？谢谢！

b*l2013-03-08 08:03

2 楼

你看的是第五版吗？网上哪里有卖电子版的？

【在 j******s 的大作中提到】

: 9.10 n boxs, height,width,depth, find the max height.
: Solution,
: Sub-problem, find the max depth that is using box b_i as bottom. Using
: recursion + cache.
: 请问各位大神算法的复杂度是多少，怎么得出来的？谢谢！

j*s2013-03-08 08:03

3 楼

电子版好像只有第四版吧

【在 b*******l 的大作中提到】

: 你看的是第五版吗？网上哪里有卖电子版的？

b*l2013-03-08 08:03

4 楼

我感觉也是，纸版的有附送光盘吗？

【在 j******s 的大作中提到】

: 电子版好像只有第四版吧

b*e2013-03-08 08:03

5 楼

this is a DP problem.

j*s2013-03-08 08:03

6 楼

没有

【在 b*******l 的大作中提到】

: 我感觉也是，纸版的有附送光盘吗？

j*s2013-03-08 08:03

7 楼

【在 b*******e 的大作中提到】

: this is a DP problem.

c*t2013-03-08 08:03

8 楼

time O(n^2) space O(n)吧

【在 j******s 的大作中提到】

j*s2013-03-08 08:03

9 楼

请问 O(n^2) 是怎么得到的，可以解释一下么，谢谢

【在 c********t 的大作中提到】

: time O(n^2) space O(n)吧

c*t2013-03-08 08:03

10 楼

对每一个box都要查一遍其他的box的stack.
不用考虑是不是从cache里得到的，因为：
如果其他box的stack已经cache, O(1)取出
如果不在cache,是要O（n)算出另一个box的stack, 但下次到这个box时则不用计算，所
以一样。每个box的stack都是算一次。

【在 j******s 的大作中提到】

: 请问 O(n^2) 是怎么得到的，可以解释一下么，谢谢

j*s2013-03-08 08:03

11 楼

首先真的感谢你的回答，我自己刚想到的分析是这样的，你的分析我没看太懂
如果没有做cache,应该是O(n^n),因为所有情况都考虑了..
做了cache,只考虑了viable solution of all lengths.
Worst case
假设所有的box如下
[0,0],[1,1],[2,2]...[n,n]
这道题就退化成了
从n...1 ，找出所有的decreasing sequence, 因为在递归的时候我们应该穷举了所有
的情况
也就相当于sum over C(n,i), i=1..n-1 = O(2^n-1)
C(n,i)表示从n...1里面随机抽出i个数删除后形成的序列..
请问这个分析有什么问题么?

【在 c********t 的大作中提到】

: 对每一个box都要查一遍其他的box的stack.
: 不用考虑是不是从cache里得到的，因为：
: 如果其他box的stack已经cache, O(1)取出
: 如果不在cache,是要O（n)算出另一个box的stack, 但下次到这个box时则不用计算，所
: 以一样。每个box的stack都是算一次。

j*s2013-03-08 08:03

12 楼

【在 c********t 的大作中提到】

c*t2013-03-08 08:03

13 楼

有问题，这题本质上是两两比较，而不是随即抽i个。比如你的例子里【2,2】只用和【
0,0】【1,1】。。。其他box比较。

【在 j******s 的大作中提到】

: 首先真的感谢你的回答，我自己刚想到的分析是这样的，你的分析我没看太懂
: 如果没有做cache,应该是O(n^n),因为所有情况都考虑了..
: 做了cache,只考虑了viable solution of all lengths.
: Worst case
: 假设所有的box如下
: [0,0],[1,1],[2,2]...[n,n]
: 这道题就退化成了
: 从n...1 ，找出所有的decreasing sequence, 因为在递归的时候我们应该穷举了所有
: 的情况
: 也就相当于sum over C(n,i), i=1..n-1 = O(2^n-1)