Grzegorz Gogolewski (gmz) wrote,
Grzegorz Gogolewski
gmz

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

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


Cross-posted from ZLog
Subscribe

  • Из жизни в террариуме

    Из мордокниги: An individual in California who tested positive for COVID-19 in late December and was vaccinated Thursday died several hours after…

  • Из жизни сорняков

    Mexican fan palm – 39%, California fan palm – 27% по мнению wildflowersearch.org – они вероятности считают по положению, в данном…

  • Аутомобильное

    Давненько не брал я в руки шашки исследовал авто сайты. Хочу купить вторую машину в семью. В принципе нам и на одной ездить особо некуда,…

  • 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

  • Из жизни в террариуме

    Из мордокниги: An individual in California who tested positive for COVID-19 in late December and was vaccinated Thursday died several hours after…

  • Из жизни сорняков

    Mexican fan palm – 39%, California fan palm – 27% по мнению wildflowersearch.org – они вероятности считают по положению, в данном…

  • Аутомобильное

    Давненько не брал я в руки шашки исследовал авто сайты. Хочу купить вторую машину в семью. В принципе нам и на одной ездить особо некуда,…