私は次のコードを持っており、このループ構造の時間の複雑さを見つけるために完全に失われています。実際はクイックソートから来たもので、このループ構造には複雑さがありますが、私はそれを理解することができません。 私はループの複雑さを計算する方法を理解できません。単純な増分または減分条件以外の真の偽条件が満たされているループです。簡単な手順を使用してループアルゴリズムの時間複雑さを計算するには？
while (i <= j) {
while (array[i] < somevalue)
i++;
while (array[j] > somevalue)
j--;
if (i <= j) {
#do something
i++;
j--;
}
};
このループの複雑さは、おおよそ#do somethingの呼び出し回数です。
最悪の場合、array[i] < somevalueもarray[j] < somevalueもいずれの繰り返しでも真ではありません。 はN/2回（片方向に丸められていてもかまいません - この場合は問題ありません）と呼ばれ、ループに入るときはi+j = Nと仮定します。私たちは、上descreaseと下位増加同時に拘束、基本的にので、サイズ2.
のステップを作るため
それはN/2だ、時間の複雑さはO(N)と同じであるO(N/2)です。
O(N)i+j = Nそれらの値が互いに出会う又は交差するときため。
iとjは、最終的に(i <= j)が偽になるようにループします。
i -> <- j
<------------------N------------------->
内部ループはどうですか？ – zubair130
コードが多少間違っています。それは、バインドされていないアクセスの配列インデックスにつながる可能性があります。 'i <配列のサイズ 'と' j> = 0'をチェックする必要があります。 –
ありがとうございます。私はそれを得たと思う。 – zubair130