theory - for ループの時間計算量の決定

Question

このループが O(n^2) であることは知っていますが、Big-Omega と Big-Theta とは何ですか? このような状況で、どのように計算しますか?

for(i = 0; i < array.length; i++) 
   for (j = 0; j < array.length; j++)
      //bla bla

Answer 1

まず、larsmans のコメントを参照してください。ループ ロジックは、除外できるほど単純であるとは限りません。議論のために、ループ ロジックが発生しないこと、ロジックが自明であること (つまり、実行される作業に影響を与える条件付きパスがないこと)、および作業単位が完全なロジックになるように定義しているとします。ループの 1 回のパスで実行されます。

この場合、上限と下限は同じです。少なくとも N^2 単位の作業単位で実行することが保証されています。Ω(N^2)、および がありますO(N^2)。下限と上限は同じです。特徴付けることができますΘ(N^2)。

ループ ロジックが自明ではなく、実際に作業単位として定義しているものに特に依存している場合、これは無意味であることを再度言及する必要があります。これらの表記のポイントは、アルゴリズムによって発生すると予想される作業量を特徴づけることです。ループを何百万回も繰り返すことができますが、本当に気にする作業がSomeExpensiveFunction()そのループ内で何回呼び出されるかであり、ロジックが 1 回だけ呼び出されることを指示している場合、この表記法には影響しません。