对于给定的代码(我只是从之前的问题中选择了一个),使用O符号表示的运行时间为O(n^2)。如果我想用Theta符号表示运行时间,那么它会是相同的吗?意思是Theta(n^2)?
for(int i=0; i<N; i++){
for(int j=1; j<N; j++){
System.out.println("Yayyyy");
if(i<=j){
System.out.println("Yayyy not");
}
}
}
对于给定的代码(我只是从之前的问题中选择了一个),使用O符号表示的运行时间为O(n^2)。如果我想用Theta符号表示运行时间,那么它会是相同的吗?意思是Theta(n^2)?
for(int i=0; i<N; i++){
for(int j=1; j<N; j++){
System.out.println("Yayyyy");
if(i<=j){
System.out.println("Yayyy not");
}
}
}
本质上:
大O符号是用于运行时间的上限。这意味着大多数算法都有几个大O边界(例如,您的算法是O(n^23)
,因为它比theta(n^23)
算法更有效)
Theta符号是用于紧密边界。并非所有算法都有明确定义的紧密边界,因为这意味着它与其他函数成比例增长。在您的示例中,因为没有办法在不打印“Yayyy not”(n^2-n)/2次的情况下完成算法,而且它永远不会运行超过此次数,它将始终与n^2成比例增长,因此具有theta(n^2)
边界!