algorithm - 分词时间复杂度

Question

我正在研究自己(这不是作业)，想弄清楚为什么人们说这个算法的时间复杂度是 O(n^2)。 对于字符串 abcd 示例，这将执行以下计算

i=0, a
i=1, ab, a
i=2, abc, bc, c
i=3, abcd, bcd, cd, d

并且总操作数为 10，比 n^2 少很多(16，其中 n=4) 有人可以解释一下为什么它的复杂度是 o(n^2) 吗？

    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }
        return dp[dp.length - 1];
    }

Answer 1

即使内循环循环少于 N 次，假设它是 n/2。因此，循环总数将为 N X N/2，即 (NXN)/2，因此对于时间复杂度，我们删除常量，因此其 O(N^2)。