なぜビーズソートはO（n）の理論上の時間複雑さを持たないのですか？

Question

Bead Sort はO（1）の理論的な時間複雑さを持っていますか？

ウィキペディアは、すべてのビーズが同時に動くと、この種のことを行うために主札を使用する場合と同じように、時間の複雑さはO（1）になりますが、ビーズは最悪の場合に旅行をしなければならず、平均的な場合はまだリストのサイズに比例していますか？

私がこの記事を誤解している場合は、はになるとO（1）時間の複雑さが発生しますか？

---

^{1また重力として知ら}ソート

Answer 1

O（1）ビーズは、すべての時間の一定量で任意に長い距離を落ちることができるモデルで複雑です。記事が述べるように、このモデルは物理的な現実を正確に反映していません。

Answer 2

ビーズソート1の理論的時間複雑度はどのようにO（1）ですか？

全てのビーズが次いで、ビーズを上から下へ順に並べることになる、平行そろばんのように同時に入ることが許されます。これはすべて一定の時間内に起こるため、複雑さはO（1）になります。

アバカスの一列に配置されたビーズの束である。アバカスのすべての行で同じことが起きるでしょう。したがって、最後の行がアバカスのすべての行にビーズで構成されるように、ビーズの最大数が最後の行に収まるでしょう。

重力のためにこのすべてが起こっている（並行して同時に各ビーズを落下させることは偶発的ではないが、理論上の前提である）。

CASE： - それは時間の複雑さの測定のために考慮する必要がないよう

*****       **** 
**********   ---->  ***** 
**************     ********** 
****       ************** 
// this happens in a short while because beads would settle to the lower surface 
// because of presence of Gravity. 

距離は、ここでは重要ではないだろう。

ウィキペディアは非現実的なケースを強調：^：

時間複雑さはO（1）になります！ビーズはすべて、同じ時間単位で同時に移動されます。 は、上記の単純な物理的な例の場合に該当します。これは複雑さが抽象的な であり、実際には実装できません。

！重点鉱山