c - たった1回のループでソート。その効率を助けてください

Question

do while ループを 1 つだけ使用した新しい並べ替えアルゴリズムを思いつきましたが、最高、平均、最悪の場合の効率を計算する方法がわからないので、計算を手伝ってください。
ループは i=1 で始まり、while ループの終了条件は i<=n-2 であり、ループ内で i の値が増加する場合もあれば、何らかの条件に基づいて i の値が減少する場合もあります。

簡単な例で説明すると、よりよく理解できると思います。私を助けてください............私
を助けてくれる人たちによろしくお願いします.....

Answer 1

いくつかの条件に基づいてi値が減少する場合があります

このあいまいさが分析を不可能にします。「条件」が常に真でありi、ゼロにデクリメントされる場合、ループは永久に実行されます。したがって、あなたの言うことに基づいて、時間の複雑さはTheta(n)無限大に及ぶ可能性があります。

時間計算量を計算する方法は、実行される操作の数を の関数として計算する (または上限を設定する) ことですn。並べ替えの場合の「操作」は通常、比較とコピー/移動を意味しますが、アルゴリズムが異常なことを行う場合は、もちろんそれを含める必要があります。