j******s
发帖数: 48 | 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*******l
发帖数: 590 | 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******s
发帖数: 48 | 3 电子版好像只有第四版吧
【在 b*******l 的大作中提到】
: 你看的是第五版吗？网上哪里有卖电子版的？
| b*******l
发帖数: 590 | 4 我感觉也是，纸版的有附送光盘吗？
【在 j******s 的大作中提到】
: 电子版好像只有第四版吧
| b*******e
发帖数: 217 | | j******s
发帖数: 48 | 6 没有
【在 b*******l 的大作中提到】
: 我感觉也是，纸版的有附送光盘吗？
| j******s
发帖数: 48 | 7
【在 b*******e 的大作中提到】
: this is a DP problem.
| c********t
发帖数: 5706 | 8 time O(n^2) space O(n)吧
【在 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******s
发帖数: 48 | 9 请问 O(n^2) 是怎么得到的，可以解释一下么，谢谢
【在 c********t 的大作中提到】
: time O(n^2) space O(n)吧
| c********t
发帖数: 5706 | 10 对每一个box都要 查一遍 其他的box的stack.
不用考虑是不是从cache里得到的，因为：
如果其他box的stack已经cache, O(1)取出
如果不在cache,是要O（n)算出另一个box的stack, 但下次到这个box时则不用计算，所
以一样。每个box的stack都是算一次。
【在 j******s 的大作中提到】
: 请问 O(n^2) 是怎么得到的，可以解释一下么，谢谢
| j******s
发帖数: 48 | 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******s
发帖数: 48 | 12
【在 c********t 的大作中提到】
: 对每一个box都要 查一遍 其他的box的stack.
: 不用考虑是不是从cache里得到的，因为：
: 如果其他box的stack已经cache, O(1)取出
: 如果不在cache,是要O（n)算出另一个box的stack, 但下次到这个box时则不用计算，所
: 以一样。每个box的stack都是算一次。
| c********t
发帖数: 5706 | 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)
|
|
