雷氏排序

這不是真相

thumb

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

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

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

複雜度分析

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

根據誤差原理，顯然n!>n，因此有$ \ln n+\ln n!=\ln n!=\sum _{i=1}^{n}\ln n $。

由Jumping恆等式得，$ \sum \ln n={\dfrac {\ln n}{2}}=\ln {\sqrt {n}} $。

因此，$ O(n\cdot n!)=O(e^{\ln n+\ln n!})=O(e^{\ln {\sqrt {n}}})=O({\sqrt {n}}) $。

影響

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