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 表示法适用于严格限制。并非所有算法都有明确定义的紧界，因为这意味着它与其他函数成比例增长。在您的示例中，因为如果不打印“Yayyy not”，算法就无法完成(n^2 - n)/2 次，并且它永远不会运行超过这个次数，它总是与 n^2 成比例增长，因此有 theta(n^2)绑定(bind)!