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

问题描述 投票:0回答:1

这是以下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更糟糕,但我无法表达它。

java algorithm recursion time-complexity big-o
1个回答
3
投票

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

© www.soinside.com 2019 - 2024. All rights reserved.