想象一下，我必须检查一个字符串的所有字母是否都在另一个字符串中。我想比较两种实现，一种是尾递归的，另一种是使用 hashMap 的。下面是两个实现:
private boolean isPossible(final String left, final String right) {
boolean toReturn = false;
if (left.isEmpty()) {
toReturn = true;
} else {
char charAt = left.charAt(0);
final int index = right.indexOf(charAt);
toReturn = index != -1 ? isPossible(left.substring(1), stringWithoutIndex(right, index)) : false;
}
return toReturn;
}
和 hashMap 解决方案:
public boolean isPossible(String left, String right) {
HashMap<Character, Integer> occurrencesMap = createOccurrenceMapFor(left);
HashMap<Character, Integer> withTheLettersInRightRemoved = removeLettersFoundIn(right, occurrencesMap);
return checkThatWeCanWriteTheMessage(withTheLettersInRightRemoved);
}
private HashMap<Character, Integer> removeLettersFoundIn(final String string, final HashMap<Character, Integer> occurrencesMap) {
HashMap<Character, Integer> lettersRemoved = new HashMap<>(occurrencesMap);
for (char c : string.toCharArray()) {
if (lettersRemoved.containsKey(c))
lettersRemoved.put(c, lettersRemoved.get(c).intValue() - 1);
}
return lettersRemoved;
}
private HashMap<Character, Integer> createOccurrenceMapFor(String string) {
HashMap<Character, Integer> occurrencesMap = new HashMap<>();
for (char c : string.toCharArray()) {
if (occurrencesMap.containsKey(c))
occurrencesMap.put(c, occurrencesMap.get(c).intValue() + 1);
else
occurrencesMap.put(c, 1);
}
return occurrencesMap;
}
private boolean checkThatWeCanWriteTheMessage(HashMap<Character, Integer> occurrencesMap) {
for (char c : occurrencesMap.keySet()){
if (withTheLettersInMagazineRemoved.get(c) > 0) {
return false;
}
}
return true;
}
我认为这两种解决方案都具有 O(n) 性能，因为它们都没有 for 循环等。但是，一旦我比较了时间，我发现 hashMap 解决方案比递归解决方案快得多。当然，这是有道理的，但我想知道为什么，因为理论上，两者都有 O(n)。我说得对吗？
最佳答案
第一个解决方案遍历第一个字符串中的每个字符，即 O(N)，但对于每个字符，它在第二个字符串中搜索匹配字符，从而给出另一个内部/嵌套的 O(N) 和 O(N^2) 总共。
第二个解决方案迭代第一个字符串 O(N)，然后迭代第二个字符串 O(N)，最后迭代仅包含有限范围字符(某些常量)的 hashmap。总和是 O(N)+O(N)+C=O(N)
关于java - 递归和非递归算法的性能，大 O 表示法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31366946/