[Coursera] Design and Analysis of Algorithm, Part 2 [Week 3]

勒个去。。coursera论坛里都是何等神人啊。。自己用C++写了算法+优化了很久，预计要5个小时出结果。。那帮人居然用python跑到了几秒钟。。
自己真是离合格码农越来越远了> <
====
原来是自己算法搞错了- -||| 当时为了理解深入点就没看slides直接编程序了，结果发现复杂度多了一级。。。现在自己的程序也跑到10秒左右了。。

Shuang7 发表于 2013-9-18 02:35
勒个去。。coursera论坛里都是何等神人啊。。自己用C++写了算法+优化了很久，预计要5个小时出结果。。那帮人 ...

此课 Part I 有份作业，计算一个有 5M+ 个节点的图的 SCC，我的代码里多了一行查询，也是导致复杂度多了一级，跑了一个晚上都没跑完…… 所以说算法优化的作用胜于超级计算机。

Shuang7 发表于 2013-9-18 15:35
勒个去。。coursera论坛里都是何等神人啊。。自己用C++写了算法+优化了很久，预计要5个小时出结果。。那帮人 ...

请问为什么我用了递归，但是还是很慢。。已经跑了很久了。。还没出答案。。。。
我的knapsack的伪代码如下：

1. if capacity == 0 or itemNumber == 0     return 0
   
2. else if capacity < weight[i]    return knapsack(itemNumber-1, capacity)
   
3. else     return max(knapsack(itemNumber-1, capacity), knapsack(itemNumber-1, capacity-weight[i]));

复制代码

我最后还是用了lecture里面说的DP方法，就是没有用n*m（n件物品，背包尺寸为m）的数组来保存每个subproblem的结果，只用了2*m的数组来cache，用了大约19秒（手机秒表计时的。。。。）
还是没搞懂题目提示的递归方法是怎么实现？

Problem Set 3:

Programming Assignment 3:

圆梦梦剧场 发表于 2013-9-22 16:48
请问为什么我用了递归，但是还是很慢。。已经跑了很久了。。还没出答案。。。。
我的knapsack的伪代码如下 ...

因为用递归时没有cache住result吧。不是只要递归算法就会快的，还是要分析其中的计算流程。你现在的代码里许多基本的单元在各次递归中重复计算了多次，所以会很慢。

Shuang7 发表于 2013-9-24 14:24
因为用递归时没有cache住result吧。不是只要递归算法就会快的，还是要分析其中的计算流程。你现在的代码里 ...

那么要cache的话还是得创建一个N*M的全局变量数组了？这不是和DP一个性质了么

圆梦梦剧场 发表于 2013-9-24 14:37
那么要cache的话还是得创建一个N*M的全局变量数组了？这不是和DP一个性质了么

我个人感觉就是这么回事。。复杂度的降低通常都来自于重复计算的减少。。也许不需要n*m？

Shuang7 发表于 2013-9-25 00:00
我个人感觉就是这么回事。。复杂度的降低通常都来自于重复计算的减少。。也许不需要n*m？

嗯，那其实也可以用一个2*M的数组或者M的数组来cache。
那我感觉DP和用了cache的递归是一个意思，只不过DP好像是bottom-up，而递归是top-down

另外版主你好猛啊，WEEK 4的作业都搞定了...

圆梦梦剧场 发表于 2013-9-25 10:14
嗯，那其实也可以用一个2*M的数组或者M的数组来cache。
那我感觉DP和用了cache的递归是一个意思，只不过 ...

嗯这好像就是coursera论坛里面大家讨论bottom-up和top-down的含义？我还以为一个是从A(1,0)算到A(1,m)和A(1,m)算到A(1,0)的区别。。

这周作业比较简单，我做得也比较仓促。。