アルゴリズムの時間の複雑さは問題ありませんか？

Question

O(n(log(2)n)^2)という複雑さのアルゴリズムを設計したいと思います。私はこれを書きました：

for(int i=1; i<=n; i++){ 
j=i; 
while(j != 1) 
    j=j/2; 

j=i; 
while(j !=1) 
    j=j/2; 
} 

O（n（log（2）n）^ 2）時間の複雑さはありますか？そうでない場合は、どこが間違っているのですか。時間の複雑さがO(n(log(2)n)^2)になるように修正できますか？

Answer 1

わずか余談：

人はコメントで言ったように、アルゴリズムが実際にO(n log n)です。これは、内側ループの複雑さに外側ループ、すなわちO(log i) x O(n)を乗算することによって得られる結果と偶然一致する。

for (int i = 1; i < n; i++) { 
    int k = i; 
    while (k >= 1) 
     k /= 2; 
     int j = i; 
     while (j >= 1) 
      j /= 2; 
    } 
} 

しかし、のは、元の複雑さが得られる方法を見てみましょう：：

をこれは、我々は単に (log n) 一部を取得するために内部ループの別の反復を追加できることを信じるようにあなたを導くことが

（スターリングの近似を使用して）

そこで提案変更が与えるだろう：

私たちが望むものではありませんどの。私は最近の個人的なプロジェクトから考えることができます

---

例は半ナイーブKDツリー構築です。擬似コードは以下の通りである：

def kd_recursive_cons (list_points): 
    if length(list_points) < predefined_threshold: 
     return new leaf(list_points) 

    A <- random axis (X, Y, Z) 
    sort list_points by their A-coordinate 

    mid <- find middle element in list_points 
    list_L, list_R <- split list_points at mid 

    node_L <- kd_recursive_cons(list_L) 
    node_R <- kd_recursive_cons(list_R) 

    return new node (node_L, node_R) 
end 

時間計算機能は、従って次式で与えられる。

をn log n部分ソートである場合。明らかに、Dn線形部分と定数Cを無視することができます。したがって：

我々が望んでいたものです。

---

ここで、同じ時間の複雑さでより簡単なコードを書くことができます。上記の導出で得られた合計を利用することができます...

そしてlog関数に渡されたパラメータがすべてのループで2で割られていることを指摘、私たちはこのようなコードを書くことができます。

for (int i = 1; i < n; i++) { 
    for (int k = n; k >= 1; k /= 2) { 
     int j = k; 
     while (j >= 1) 
      j /= 2; 
    } 
} 

これは、「ナイーブ」が、正しくないように見えます（jはkには依存しませんでしたが、kはnの代わりにiに依存していました）。

---

EDIT：いくつかの数値意図したとおりに複雑であることを確認するテスト：

テスト機能コード：

int T(int n) { 
    int o = 0; 
    for (int i = 1; i < n; i++) 
     for (int j = n; j >= 1; j /= 2) 
      for (int k = j; k >= 1; k /= 2, o++); 
    return o; 
} 

数値結果：

n   T(n) 
------------------- 
2   3 
4   18 
8   70 
16   225 
32   651 
64   1764 
128   4572 
256   11475 
512   28105 
1024  67518 
2048  159666 
4096  372645 
8192  860055 
16384  1965960 
32768  4456312 
65536  10026855 
131072  22413141 
262144  49807170 
524288  110100270 

は、その後、私はsqrt(T(n)/n)プロットnに対して複雑さが正しければ、log(n)グラフ、または直線をログスケールの横軸にプロットするとよいでしょう。

そして、これは我々が得るもの確かです：