java - 为什么这个 O(n^2) 代码的执行速度比 O(n) 快？

Question

这个问题在这里已经有了答案:

Can an O(n) algorithm ever exceed O(n^2) in terms of computation time? (6 个回答)

关闭 3年前。

我已经编写了两种方法的代码来找出 LeetCode 上字符串中的第一个唯一字符。

Problem Statement: Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Sample Test Cases:

s = "leetcode" return 0.

s = "loveleetcode", return 2.

方法 1 (O(n))(如果我错了，请纠正我):

class Solution {
    public int firstUniqChar(String s) {

        HashMap<Character,Integer> charHash = new HashMap<>();

        int res = -1;

        for (int i = 0; i < s.length(); i++) {

            Integer count = charHash.get(s.charAt(i));

            if (count == null){
                charHash.put(s.charAt(i),1);
            }
            else {
                charHash.put(s.charAt(i),count + 1);
            }
        }

        for (int i = 0; i < s.length(); i++) {

            if (charHash.get(s.charAt(i)) == 1) {
                res = i;
                break;
            }
        }

        return res;
    }
}

方法 2 (O(n^2)):

class Solution {
    public int firstUniqChar(String s) {

        char[] a = s.toCharArray();
        int res = -1;

        for(int i=0; i<a.length;i++){
            if(s.indexOf(a[i])==s.lastIndexOf(a[i])) {
                res = i;
                break;
            }
        }
        return res;
    }
}

在方法 2 中，我认为复杂度应该是 O(n^2)，因为 indexOf 在这里执行 O(n*1)。

但是当我在 LeetCode 上执行这两种解决方案时，方法 2 的运行时间为 19 毫秒，方法 1 的运行时间为 92 毫秒。我很困惑；为什么会这样？

我认为 LeetCode 会针对最佳、最差和平均情况对小输入值和大输入值进行测试。

更新:

我知道 O(n^2 算法) 对于某些 n < n1 可以表现得更好。在这个问题中，我想了解为什么在这种情况下会发生这种情况。即方法 1 的哪一部分使其变慢。

LeetCode link to the question

Answer 1

考虑:

• f₁(n) = n²
• f₂(n) = n + 1000

显然 f₁ 是 O(n²) 而 f₂ 是 O(n)。对于小的输入(例如，n=5)，我们有 f₁(n) = 25 但 f₂(n) > 1000。

仅仅因为一个函数(或时间复杂度)是 O(n) 而另一个是 O(n²) 并不意味着前者对于所有 n 值都较小，只是存在是一些 n 超出这将是这种情况。