假设您正在和您的 friend 玩以下 Flip Game:给定一个仅包含这两个字符的字符串:+ 和 -，您和您的 friend 轮流将两个连续的 "++" 翻转为 "--"。当一个人不能再移动时，游戏结束，因此另一个人将成为赢家。
编写一个函数来判断起始玩家是否可以保证获胜。
例如，给定 s = "++++"，返回 true。起始玩家可以通过翻转中间的“++”成为“+--+”来保证获胜。
这是我的代码:
public boolean canWin(String s) {
if(s==null || s.length()<2) return false;
char[] arr=s.toCharArray();
return canWinHelper(arr);
}
public boolean canWinHelper(char[] arr){
for(int i=0; i<arr.length-1; i++){
if(arr[i]=='+' && arr[i+1]=='+'){
arr[i]='-';
arr[i+1]='-';
boolean win=!canWinHelper(arr);
arr[i]='+';
arr[i+1]='+';
if(win) return true;
}
}
return false;
}
它有效，但我不确定如何计算这里的时间复杂度，因为该函数将继续调用自身，直到返回 false。有人在这里分享一些想法吗？
同样在查找过程中，我们会遇到重复计算，所以我想我可以使用hashmap来避免这些重复。键:字符串，值: boolean 值。
我使用 HashMap 更新的代码:
public boolean canWin(String s){
if(s==null || s.length()<2) return false;
HashMap<String,Boolean> map=new HashMap<String,Boolean>();
return helper(s,map);
}
public boolean helper(String s, HashMap<String,Boolean> map){
if(map.containsKey(s)) return map.get(s);
for(int i=0; i<s.length()-1; i++){
if(s.charAt(i)=='+' && s.charAt(i+1)=='+'){
String fliped=s.substring(0,i)+"--"+s.substring(i+2);
if(!helper(fliped,map)){
map.put(s,true);
return true;
}
}
}
map.put(s,false);
return false;
}
还是想知道这里的时空复杂度怎么分析？
最佳答案
取 n = arr.length - 1
首先，您有 n 个递归调用。对于每一个，您都删除了两个 +，因此每个将最多有 n-2 次递归调用，依此类推。
所以你最多有 n+n(n-2)+n(n-2)(n-4)+... 递归调用。
本质上这是 n!!(1+1/2+1/(2*4)+1/(2*4*8)+...) 因为 1+1/2+1/(2 *4)+1/(2*4*8)+...收敛，≤2，你有O(n!!)
关于内存，对于每个递归调用，你有一个长度为 n 的数组，所以你有 n + nn + nnn + n ... (n/2 次) ... *n = n(n^(n/2)-1)/(n-1) 这是 O(n^(n/2))
这显然表明性能并不比穷举搜索好多少。
对于散列改进，您要求提供您已设法使用代码创建的所有可能组合。但是，您的代码与实际创建所有组合的代码没有太大区别，除了您将两个 + 替换为两个 - 之外，这通过某种因素降低了复杂性，但没有降低它的水平.总的来说，最坏的情况与 n/2 个位置之间的位组合数相同，即 2^(n/2)。观察哈希函数本身可能有一些隐藏的日志，所以总的复杂度是搜索 O(2^(n/2)*ln(n/2)) 和内存 O(2^(n/2))。
这是最坏的情况。但是，如果有无法取胜的安排，当没有取胜策略时，以上就是您需要指望的复杂性。
平均场景的问题就是你能/不能赢的情况的数量以及它们在所有安排中的分布问题。这个问题与您的算法没有太大关系，需要一套完全不同的工具才能解决。
经过片刻检查上述推理是否正确和切题后，我会对结果感到非常满意，因为它告诉了我所有我需要知道的事情。你不能指望你会有一个有利的安排，我真的怀疑你只有 0.01% 的最坏情况安排，所以无论如何你都需要准备最坏的情况，除非这是一些特殊的项目，否则 -大胆的计算是您的 friend 。
无论如何，这些类型的计算是为了正确准备测试用例，而不是为了正确和最终实现。使用这些测试，您可以找到 O() 中真正隐藏的因素，同时考虑编译器、内存消耗、分页等。
当然，我们仍然不能保持原样，我们总是可以改进粗略的推理。例如，您实际上在每一步都没有 n-2，因为它取决于奇偶校验。例如对于++++++++... 如果你替换第三个+++--+++++... 很明显你将有 n-3 个，而不是 n-2 个递归调用，甚至 n-4。所以一半的调用可能有 n-3 个递归调用，这将是 n/2(n-3)+n/2(n-2)=n(n-5/2)
观察到因为 n!=n!!(n-1)!!我们可以取 n!!≈√n!, n!=n!!!(n-1)!!!(n-2)!!!或 n!!!≈∛n!这可能会得出一个结论，我们应该有类似 O((n!)^(5/2)) 的东西。测试会告诉我我们可以在 O((n!)^(x)) 中减少多少 x=3。
(寻找一种特定形式的复杂度是很正常的，就像我们有 O((n!)^(x) 一样)，尽管它可以用不同的方式表达。所以我会继续复杂度形式 O( (n!)^(x)),1≤x≤3)
关于java - 这里怎么分析时间复杂度呢？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34254085/