java - 递归和非递归算法的性能，大 O 表示法

Question

想象一下，我必须检查一个字符串的所有字母是否都在另一个字符串中。我想比较两种实现，一种是尾递归的，另一种是使用 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)。我说得对吗？

Answer 1

第一个解决方案遍历第一个字符串中的每个字符，即 O(N)，但对于每个字符，它在第二个字符串中搜索匹配字符，从而给出另一个内部/嵌套的 O(N) 和 O(N^2) 总共。

第二个解决方案迭代第一个字符串 O(N)，然后迭代第二个字符串 O(N)，最后迭代仅包含有限范围字符(某些常量)的 hashmap。总和是 O(N)+O(N)+C=O(N)