JAVA: BigO 算法 - equalsIgnoreCase 和 CompareTo

Question

BigO 算法是否适用于：

//O(N)
public boolean isSameName(Candidate otherCan) {
    return this.name.equalsIgnoreCase(otherCan.getName());
}

和

//O(N)
public int compareTo(Candidate otherCan) {
    return this.name.compareToIgnoreCase(otherCan.getName());
}

和

//O(N)
public int getTotalVotes() {
    int t = 0;
    for(int i = 0; i < 4; i++) {
        t += stateVotes[i];
    }
    return t;
}

和

//O(1)
public Candidate(String name) {
    this.name = name;
}

你能为这些算法提供 BigO 算法吗？还是仅适用于循环和数组？这些合适吗？

Answer 1

你的问题有点令人困惑，因为每段代码都有时间和space复杂性。根据定义，代码需要一定的时间，而该代码的数据使用一定数量的 space（即使 time/space 为零）。

具体来说，前两个是否 O(N) 取决于 Java 中的底层代码，但它很可能是正确的。

第四个，字符串赋值，这是一个参考副本O(1)。

然而，第三个不是 O(N) 因为实际上没有 N 涉及。无论 stateVotes 的大小如何，它都正好迭代四次，所以应该是 O(1).

JAVA: BigO algorithm - equalsIgnoreCase and CompareTo