从m个数中任取n个数的组合算法和时间复杂度分析!
请给出时间复杂度是多项式的算法,分析最好能详细一点。多谢!
[解决办法]
lz要总个数数目,还是要所有组合?
若要的是计算总个数的程序,那太简单了。
若要的是列举出所有组合,那是没有“时间复杂度是多项式的算法”的!
任何算法列举出所有组合都得遍历所有组合吧?那样复杂度怎么可能是“多项式”级?
只能减少常数因子,不可降低复杂度级别!
[解决办法]
假设K次操作产生1个组合,那么运算次数为K*C(m,n) [ C(m,n)为m个取n个的组合数 ]
我们只能降低K的数量,不可降低C(m,n)的阶。
[解决办法]
如果数据有限制,并且是找所有组合中的最优一种组合,可以考虑dp,是多项式!如果要打印出所有组合,那真没办法了,明显是一个组合的枚举问题