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

您的问题有点令人困惑，因为每段代码都具有时间和空间复杂性。根据定义，代码会占用一定的时间，而该代码的数据会占用一定的空间(即使该时间/空间为零)。

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

对于第四个，字符串赋值，这是一个引用副本，它是O(1)。

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