用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");
    }
}
}

- FranXh

---

在这种情况下也是一样的，因为时间复杂度的上限和下限都由一些（两个不同的）函数所主导，而这些函数又被 x² 所主导。 - nhahtdh

如果这是一份作业，你应该将其标记为作业。 - Tyler Treat

你的问题在这里得到了答案：https://dev59.com/cnRB5IYBdhLWcg3w6LV3 - natewelch_

Answer 1

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

- olagjo

Answer 2

简而言之，BigO(n^2) 表示您的算法不会超过 ~n^2 的时间。BigTheta(n^2) 表示您的算法不仅不会超过 ~n^2 的时间，而且不会少于 ~n^2 的时间。

- Eli Burmin