algorithm - 2 つのループの時間計算量 (アクション数) を計算するには?

Question

2 つのループの時間計算量を計算する方法がわかりません。

i は 1 から n まで実行されます: 1,2,3,4,5,...,n

j は 1 から i までです。1,2,4,8,...,i

i = 1 の場合
j: 1
回のループ実行: 1 回

i = 2 の場合
j: 1,2
ループ実行: 2 回

i = 3 の場合
j: 1,2
ループ実行: 2 回

i = 4 の場合
j: 1,2,4
ループ実行: 3 回

i = 5 の場合
j: 1,2,4
ループ実行: 3 回
.... i = nの場合
j: 1,2,4,8,...,n ループ実行: logn+1 回

したがって、ループが実行されます (回数): 1+2+2+3+3+3+3+4+...+(logn+1)

だから私は恒常性を理解していません。
これのシグマを作成するにはどうすればよいですか?

Answer 1

サイクルの Big-O を評価しようとしており、他に依存関係がないため、次の見積もりを使用できます。

O(Full Cycle) = O(Outer Cycle)*O(Inner Cycle) = O(N)*O(log2(N)) = O(N log(N))

j*2 < i(2 番目の見積もりは、単純に定義によるものです。なぜなら、大きな O を探しており、サイクルがとまで繰り返されることがわかっているからですi < n)