JAVA：戈算法 - equalsIgnoreCase和的CompareTo

是一个比戈算法适用于：JAVA：戈算法 - equalsIgnoreCase和的CompareTo

//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算法，还是仅仅用于循环和数组？那些合适吗？

来源

2016-12-16 M.A

您的'getTotalVotes'方法是O（1），因为步数不取决于输入的大小（它总是4步） –

你的问题是一个小混淆因为每一段代码有一个时间和空间的复杂性。根据定义，代码需要一定量的时间，并且该代码使用一定数量的空间（即使该时间/空间为零）的数据。

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

对于第四个字符串分配，这是一个参考副本，它是O(1)。

但是，第三个是而不是O(N)因为实际上没有N涉及。无论stateVotes的大小如何，它都会重复四次，所以应该是O(1)。

来源

2016-12-16 02:38:28 paxdiablo

哦，所以每个循环都必须有一个BigO算法？但如果它有一个限制，例如重复5或6，那么它是O（1），而不是O（N）。什么是BigO算法的Try-While和While？ –

@ M.A，是的，甚至是非循环:-)假设你正在讨论最糟糕的情况，一个确定的限制循环将是O（1）big-O :-)平均情况可能不同。在'while'方面，它完全取决于你遗漏的位（控制循环的条件） - while'本身就是一个条件检查和跳转，它往往是O（1），但是，当然，条件本身可能是非O（1）。 – paxdiablo

示例4中没有字符串复制。它只是将对该字符串的引用赋予另一个变量。它是O（1），这在JVM规范中得到了修复 - 它不能依赖于Java在Java中的实现方式，因为对象引用分配不是多态操作。 –

JAVA：戈算法 - equalsIgnoreCase和的CompareTo

回答

相关问题