Java 内置函数 Collections.frequency(list, element) 的复杂度是多少？

Question

下面的代码是针对 String 的 ArrayList。我想知道Collections.frequency()函数的复杂度是多少。

List<String> list = new ArrayList<>();
list.add("sample");
list.add("sample1");
list.add("sample");
list.add("sample");
list.add("sample");
list.add("sample");
System.out.println("sample is repeated : " + Collections.frequency(list, "sample"));

Answer 1

Collections.frequency 具有以下实现（在 Java 9 中）：

public static int frequency(Collection<?> c, Object o) {
    int result = 0;
    if (o == null) {
        for (Object e : c)
            if (e == null)
                result++;
    } else {
        for (Object e : c)
            if (o.equals(e))
                result++;
    }
    return result;
}

所以是O(n)。