首页 > 试题广场 >

关于线性规划的算法复杂度以下哪些是正确的？

[单选题]

simplex在多项式复杂度的时间内可以解决线性规划问题

simplex不是多项式复杂度，而且线性规划的问题不可以在多项式时间内求解

线性规划的问题可以在多项式时间内求解，但是simplex不是多项式复杂度

因为线性规划的可行域总是凸集，所以simplex算法才能在多项式时间复杂度内解决线性规划问题

查看正确选项

牛客HFL

选C

发表于 2023-08-01 17:49:26 回复(0)

910号

单纯形法是一种迭代算法，通过不断地移动到相邻的可行解来逐步逼近最优解。它的时间复杂度取决于问题的规模，并且在最坏情况下具有指数级复杂度。更准确地说，如果问题有n个变量和m个约束条件，则单纯形法的最坏情况时间复杂度为O(2^n)。

发表于 2023-08-01 12:53:51 回复(0)

提交观点

问题信息

职能快手算法工程师财务 2019

上传者：小小

难度：

2条回答 25收藏 1146浏览

扫一扫，把题目装进口袋