代码之家 › 专栏 › 技术社区 › ineedahero

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

big-o time-complexity recursion algorithm java

ineedahero · 技术社区 · 7 年前

problem

基本上,您有一个由“-”和“+”字符组成的字符串:

++-++++

你把两个连续的“+”翻成“-”,然后你的朋友也这样做,然后回到你身边,依此类推。一旦有人不能采取行动,他们就输了。

所以在上面的游戏中,如果你先走,你可以通过翻转最后两个“+”,或者中间两个“+”(想想看)。

下面是一个算法,它可以解决先走的玩家是否获胜:

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,但我无法表述。

1 回复 | 直到 7 年前

HackerBoss 7 年前

在最坏的情况下,第一个玩家无法获胜,循环将经历所有迭代。把问题的大小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)个可能的字符串是从包含“+”和“-”的起始字符串派生出来的。在此之后,所有递归调用都是常量时间(摊销)。

推荐文章

RASEL MAHMUD · 为什么以及如何在is_even()函数内的IF条件中递归X变量在满足0后递增?[副本]

9 月前

MMedina · 将powershell应用于子文件夹

11 月前

YorSubs · Linux中遍历目录的时间不同方法[关闭]

11 月前