雷氏排序

雷氏排序，是一種廣為人知的排序算法，由雷紹武發明，後由雷紹武和Jumping共同證明其複雜度，因此有時也稱為雷紹武-Jumping算法。

這不是真相

thumb thumb

本維基上除明確標為非超理的內容之外，一切內容均為虛構，完全不可信。 無論描述看起來再真實，它也不是真的！請務必注意！

考慮一個序列和一位猴星人，該猴星人每次將該序列隨機排列，並檢驗它是否有序。若有序則算法終止，否則重複進行以上步驟。

複雜度分析

單次隨機排列的時間複雜度為O(n)，平均需要排列n!次，總複雜度為<math>O(n\cdot n!)=O(e^{\ln n+\ln n!})</math>。

根據誤差原理，顯然n!>n，因此有<math>\ln n+\ln n!=\ln n!=\sum_{i=1}^n\ln n</math>。

由Jumping恆等式得，<math>\sum\ln n=\dfrac{\ln n}{2}=\ln\sqrt{n}</math>。

因此，<math>O(n\cdot n!)=O(e^{\ln n+\ln n!})=O(e^{\ln\sqrt{n}})=O(\sqrt{n})</math>。

影響

該算法的發明極大地提高了各類軟件的運行效率，同時說明：可以在不訪問全部元素的前提下對序列進行排序。顯然，這與超理學基本原理說不準原理是高度相符的。該算法為超理數學的發展做出了不可磨滅的貢獻。