java - 使用 O 和 Theta 表示的运行时间

Question

对于给定的代码（我只使用我之前的问题中的一个），使用 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");
    }
}
}

Answer 1

本质上：大 O 表示法用于运行时间的上限。这意味着大多数算法都有几个大 O 边界（例如，您的算法是O(n^23)因为它比theta(n^23)算法更有效）
Theta-notation 用于紧密边界。并非所有算法都有明确定义的紧密界限，因为这意味着它与其他函数成比例增长。在您的示例中，因为没有打印“Yayyy not” (n^2 - n)/2 次，算法就无法完成，并且它永远不会运行超过这个次数，它总是与 n 成比例增长^2，因此有theta(n^2)界！

Answer 2

为了使这个简短易懂，BigO(n^2) 意味着您的算法不会花费超过 ~n^2 的时间。BigTheta(n^2) 意味着你的算法不会超过~n^2 时间，也不会少于~n^2 时间。