algorithm - このアルゴリズムの複雑さ

Question

したがって、次のようなアルゴリズムがあります。

for i=0:360

 C...

 for j=0:a_j[i]

   C...

   for t=0:a_t[i][j]

     C...
   end
 end
end

したがって、3 つのループがありますが、両方の内側のループは外側のループの値に依存します。Big O表記の複雑さを測定するにはどうすればよいですか?

また、これらのループ間にメモリ割り当てがある場合はどうなりますか? それらはCとしてカウントされますか？

Answer 1

コードの残りの部分については何も言っていないので、残りは一定の複雑さの原始的な操作であると仮定します。

2 つの配列のエントリが定数値より小さい場合、複雑さは次のとおりですO(1)。処理は、コードの外部からの値の入力に依存しません。それらが入力変数の関数である場合、複雑さはそれらがそれらの配列に処理される関数に依存し、この場合はより具体的にする必要があります。

Answer 2

a_jとが正確に何であるかはわかりませんa_t。a_jとa_tが一定の場合、複雑さはO(1)です。a_jとa_tがである場合n、これは入力変数を意味する可能性があり、複雑さを計算する必要があります。

a_jつまり、このプログラムの複雑さは、とをどのように定義するかによって決まりますa_t。

とにかく、あなたのプログラムが実行するループの数を計算できます。

Pythonで書かれたコードは次のとおりです。

ret = 0
for i, v in a_j:
    ret += v * sum(a_t[i])
if not ret: ret = 1
ret *= 360

それが役に立てば幸い。