问答

当前位置

记忆化搜索怎么算复杂度?

老师您好,
请问, 记忆化搜索的复杂度一般怎么算呢?

比如一个道Google 老题:
You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".
如下解法的复杂度是什么呢?谢谢!
public boolean canWin(String s) {
if(s==null || s.length<2){
return false;
}

    Set<String> winSet = new HashSet<String>(); //memo

    return canWinHelper(s, winSet);
}

private boolean canWinHelper(String s, Set<String> winSet){
    if(winSet.contains(s)) return true;

    for(int i=0; i<s.length()-1; i++){
        if(s.charAt(i) == '+' && s.charAt(i+1) == '+'){
            String sOpp = s.subString(0, i)+"--"+s.subString(i+2);
            if(!canWin(sOpp, winSet)){
                winSet.add(s);
                return true;
            }
        }
    }

    return false;
}

1 个回复

2016-08-16 马同学

记忆化搜索的复杂度和普通递推的dp计算的方式差不多。
O(状态个数 * 每个状态转移的复杂度)

我觉得这里的状态的个数2^(n/2)个,状态转移的复杂度是n,所以时间复杂度大约是O(2^(n/2) * n), 当然分析状态的个数的时候可以更详细准备一些,我只是一个估计。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1