java - 这个 5 行 Java 算法的时间复杂度是多少？

Question

这是以下 problem 的解决方案

基本上，您有一串“-”和“+”字符:

++-++++

您将两个连续的“+”翻转为“-”，然后您的 friend 也这样做，然后返回给您，依此类推。一旦有人不能出手，他们就输了。

所以对于上面的游戏，如果你先走，你可以通过翻转最后两个“+”或中间两个“+”(考虑一下)来获胜。

这是一个解决先手是否获胜的算法:

public boolean canWin(String s) {
    for (int i = 0; i < s.length() - 1; ++i)
        if (s.charAt(i) == '+' && s.charAt(i + 1) == '+' && 
            !canWin(s.substring(0, i) + "--" + s.substring(i + 2)))
                return true;
    return false;
}

基本上，该算法会递归地说“如果先手玩家能够将棋盘缩小到先手玩家输的状态，那么他就赢了”。

这是我对时间复杂度的看法:

令 N 为棋盘上的字符数。

在最坏的情况下，有 N-1 步(如果全部为 '+')。每一步都会让棋盘(最坏情况下)只缩小 2 步。

但后来我卡住了。我知道它比 N * (N-2) * (N-4) * ... * 1 更糟糕，但我无法公式化它。

Answer 1

在最坏的情况下，第一个玩家无法获胜，循环将进行所有迭代。将问题大小 n 设为输入字符串中加号的数量，我们的运行时间为 T(n)=(n-1)T(n-2)=(n-1)(n-3) T(n-4)=...=O(n!!)。在这里，n!!是双阶乘。这明显比指数差，这对于这个问题来说是相当可怕的。您可以使用如下动态规划大大改进此界限:

Set<String, Boolean> canWinMap = new HashMap<>();

public boolean canWin(String s) {
    if (canWinMap.hasKey(s)) {
        return canWinMap.get(s);
    }
    for (int i = 0; i < s.length() - 1; ++i)
        if (s.charAt(i) == '+' && s.charAt(i + 1) == '+' && 
            !canWin(s.substring(0, i) + "--" + s.substring(i + 2)))
                canWinMap.put(s, true);
                return true;
    canWinMap.put(s, false);
    return false;
}

然后最坏情况受指数(可能乘以线性项)的限制，因为从包含“+”和“-”的起始字符串派生的字符串只有 O(2^n) 种可能。此后，所有递归调用都是恒定时间(摊销)。