您显示的值迭代的更新方程是时间复杂度$O(|\mathcal{S}\times\mathcal{A}|)$每次更新到单个$V(s)$估计，因为它遍历所有要执行的操作$\text{max}_a$以及所有接下来的状态$\sum_{s'}$.

您找到的来源可能将整个状态空间扫描计为“迭代”，即$\forall \space s \in \mathcal{S}: V_{k+1}(s) \leftarrow \text{max}_a \sum_{s'} T...$这增加了另一个因素$|\mathcal{S}|$使整体复杂性$O(|\mathcal{S}\times\mathcal{S}\times\mathcal{A}|)$或者$O(|\mathcal{S}|^2|\mathcal{A}|)$

这种迭代的定义是有意义的，因为基本值迭代算法需要扫描整个状态空间才能收敛。这也符合标准收敛测试，该测试在每次完整扫描后进行，并检查扫描结束时最大的绝对更新是什么——如果它低于某个准确度目标值，则该过程被宣布完成。