は、次のコードを考えてみましょう：時間複雑さに疑問がある！
for(i = n-1; i >= 0; i--)
{
if(str[i] == ' ')
{
i += 2; // I am just incrementing it by 2, so that i can retrieve i+1
continue;
}
// rest of the code with many similar increments of i
}
セイは、ループが無限大にまでなったことがないと私は多くのそのような増加やデクリメントでループを横断した場合、私は複雑さが順番NまたはNのではないでしょう確信していると仮定します平方。しかし、そのような種類のソリューションには一般化された複雑さがありますか？
P.S：私は知っているが、最悪のコードをそれ `s、しかし、あなたは、文字列内のスペースを持っている場合は、まだ
:-)それを試してみることにしたかったこれは無限ループ（無限の複雑さ）です。 continueを使用しているため、forに戻り、i + 2から開始します。
文字列にスペースが1つしか含まれていない場合、このプログラムは無限の回数実行されます。文字列がすべてのspacesで構成されている場合に限り無限に進みます。また、intまたはlongの場合、 。 – Algorithmist
これは逆ループです。「i」は最大値から始まり、その値が減少します。だからスペースに当たったら 'i'がインクリメントされるので、ループは2つの位置から開始し、同じスペースに当たるので、最初のスペースは決して通過できません** – Aliostad
strは、このトラバーサルの過程で変化しないと仮定します。
あなたは逆方向に移動しています。スペースをヒットすると、インデックスが1つ前に移動します。つまり、次のデクリメントで再びスペースに当たってから再び前に移動します。すなわち、ループが無限ではないと主張します。有効ではないようです。
iがとるパスに変更可能な状態がない場合は、無限ループに入るか、n以下の手順でループを終了します。後者の場合、最悪の場合のパフォーマンスはO(N)になります。
ループが他のいくつかの状態を変更し、その状態がパスに影響を及ぼす場合、状態と突然変異プロセスを理解することなく複雑さを予測することは不可能です。
（書かれているように、コードは無限ループに入ります...ループの最後のセクションには、それを防ぐために何かをしない限り。）
だから我々は 'i'がで修正されていることを想定していますループの下部も同様ですか？ – Eric
あなたの完全なコードは見えませんが、実行時間が 'Theta（N）'ではないことを確かめることはできません。 – phimuemue
文字列の最初の文字がスペースの場合は、配列の境界からインデックスを作成します。したがって、あなたのプログラムは強制的に中止されるので、アルゴリズムを終了するのに無限に時間がかかります！ – Eric