0

このループのシーケンス全体がO（n）であることをどのように示しますか？それともO（n）ですか？一見、ダブルループを見るだけでO（n ^ 2）だと思うかもしれませんが、そうではないと思います...

int i = 0;
int arr[N];
int idx = 0;
for (i = 0; i < 2; i++)
{
    for (j = 0; j < N/2; j++)
    {
      idx = (i * N/2) + j;
      foo(arr[idx]);
    }
 }

4

1 に答える 1

2

外側のループは一定であるため、ループは次の場合と同じです。

for (j = 0; j < N/2; j++)
{
  idx = (0 * N/2) + j;
  foo(arr[idx]);
  idx = (1 * N/2) + j;
  foo(arr[idx]);
}

これにより、実際にはコードの意図も非常に明確になりますが、ご覧のとおり、操作の量はNに比例して変化するため、指数関数的成長ではなくO（N）の複雑さです。午前8時30分で寝ていないので、これ以上説明することはできませんが、あなたが私の要点を理解していると思います。

于 2012-10-23T00:40:05.950 に答える