我知道在复杂性方面,O(logn)比O(n)快,后者比O(nlogn)快,后者比O(n2)快.但是O(n2)和O(n2log),或者O(n2.001)和O(n2log)呢:
T1(n)=n^2 + n^2logn
这个功能的大哦和欧米茄是什么？还有,什么小哦？与:
T2(n)=n^2.001 + n^2logn
现在大喔有什么区别吗？我无法理解如何将logn与n的幂进行比较.如在,登录大约n ^ 0.000000 ... 1或n ^ 1.000000 ... 1？
如果给你一组具有值和重量的项目:[(w1,v2),(w2,v2),...(wn,vn)],以及两个容量相等的背包Knap1和Knap2,目标是确定可以分别进入Knap1和Knap2的项目S1和S2的最佳子集是什么,并最大化背包的值和容量.
解决这个问题的一种不正确的方法是首先使用所有项目作为候选项的DP编程算法填充Knap1,然后使用Knap1中的剩余项目填充Knap2.
我不明白为什么如果两个背包具有相同的容量,这个算法是不正确的.有人可以解释或举例吗？