Grzegorz Gogolewski (gmz) wrote,
Grzegorz Gogolewski
gmz

Чем я хуже Гильберта?

Пресловутый алгоритм сортировки пяти элементов за семь сравнений иногда даёт результат после 6го сравнения. Я не поленился, написал программульку, и оказалось, что среднее число сравнений - 6.93 (точнее 832/5! или 104/15).
Вот более интересная задача: доказать, что пресловутый алгоритм даёт наилучшее среднее число сравнений. Ну, или найти более шустрый в среднем алгоритм.


Cross-posted from ZLog
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 21 comments