2回答

liuyubobobo

2019-01-16

已采纳

为什么sort以后贪心不是全局最优解？sort的复杂度是O(nlogn)，贪心的复杂度是O(n)；而动态规划怎么也是O(n^2)的：）即使动态规划能优化到O(n)级别，和排序+贪心的O(nlogn)只相差一个logn，完全没有影响。

动态规划的意义在于将指数计算法用空间优化成多项式算法。学习动态规划，很容易把所有的问题都想成是必须使用动态规划解决的问题：）

另外，如果想要设计的算法没有明确要求如何处理？当然是要先将要求（需求）明确。在设计算法前，必须先明确要解决的问题是怎样的。在实际工作中，根本没有搞清楚自己要解决的问题是怎样的，有怎样的约束条件，就要设计算法，是我见过的最常见的问题，而非算法设计问题。其实仔细想一想，这和做外包很像。大多数外包问题，根本不是技术问题，而是需求不明确：）

最后，大多数瀑布流算法，就是先将每一列排满，然后每一列记录一个高度值，后续的图片排在当前高度至最低的列中，依次类推：）如果愿意的话，可以对所有列的高度维护一个优先队列。但由于大多数瀑布流页面的列数很少，肯定是个位数，线性扫描都是没问题的：）

至于你说的问题，我没有细想，很有可能是一个NP难的问题。所以根本不存在多项式级别的算法：）

继续加油！

0

1

小学生6年级

非常感谢！

2019-01-16

共1条回复

小学生6年级

提问者

2019-01-16

我之前描述的有误，我的意思是使这几份相差的和最小。就是让这几份尽可能接近，这种没有明确要求的该如何处理呢？比如说典型的例子就是前端的瀑布流，后端给了一堆图片数据，我希望分成三列排放，让三列最后的高度相差小。当然，我可以先 sort 以后基于贪心的思路插入 DOM，但是这肯定不是全局的最优解。因此想请教下老师怎么做？

如果放两列的话，动态规划完全没有问题。可是三列，四列就做不了啊。比如说四列，我想的是先分成两列得到的 SUM/2，可是仔细一想发现还是不能保证接着拆分以后差能够是最小的。三列就更没有头绪了。。。

0

0