0

我正在浏览与动态编程相关的这个页面。我对给定的复杂性感到非常困惑

在此处输入图像描述

在第三种情况下,复杂度为 $O(n^2)$。我不确定它是怎么变成这样的。任何人都可以请详细说明。这里的复杂性是如何计算的。

4

1 回答 1

1

如果 i 和 j 的范围都在 1 到 n 之间,我可以通过考虑将 i 固定在 1 而 j 从 1 到 n 的范围来查看 n^2 个子问题。然后对 i 1-n 的所有值执行相同的操作。但是图片和集合符号似乎暗示 j > i (一个连续的、唯一的集合),所以我认为这让它有点混乱。我在想象 i=2, j=1... 可以是 x2, x3 (将 j 解释为我们想要从 2 开始的 x 的数量?)或 x2, x1 (将 j 解释为索引)...。

于 2012-10-01T14:50:44.307 回答