暴力遍历排课调度问题所有可能解的时间复杂度如何计算

你之前得出的O((m*n)^25)结果是错误的，正确推导过程如下：

前置说明 #

题目中提到的「相邻两个解仅改动某一个教学班的某一门课程的时间槽」属于启发式搜索的邻域规则，暴力遍历无需遵循该规则，因此该条件不影响复杂度计算，暴力遍历的核心是枚举所有符合要求的可行解。

分场景计算结果 #

场景1：无冲突约束（仅要求所有课程分配时间槽，允许同一教学班同一时间排多门课） #

总共有n*m门需要分配时间的课程，每门课可以独立选择25个可用时间槽中的任意一个，总可行解数量为25的(n·m)次方，对应时间复杂度为 O(25^{n·m})。

场景2：带基础冲突约束（同一教学班同一时间只能排一门课，现实排课的默认规则） #

每个教学班需要从25个时间槽中选出m个不重复的槽，分配给自己的m门课，单个班的可选方案为排列数：
P(25,m) = 25 × 24 × … × (25 - m + 1) = 25!/(25-m)!
n个班的总方案数为单班方案数的n次方，对应时间复杂度为 O( (\frac{25!}{(25-m)!})^n )。
如果m远小于25，该复杂度可近似为O(25^{n·m})，和无约束场景的量级一致。

错误原因说明 #

你之前的推导颠倒了底数和指数的逻辑关系。只有当场景变为「给25个时间槽各分配1门课，总共有n*m门课可选」的时候，才会得到O((n·m)^25)的复杂度，和当前「给n·m门课各分配1个时间槽，总共有25个槽可选」的排课场景逻辑完全相反。

内容的提问来源于stack exchange，提问作者Awais Shahid