Grzegorz Gogolewski (gmz) wrote,
Grzegorz Gogolewski
gmz

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

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


Cross-posted from ZLog
Subscribe

  • Культурологическое

    3, 4, 6 симметрия в живой природе тоже есть, оттуда всё эти звезды и взяты? На фото – мандарин.

  • Природу, мать вашу

    В качестве компенсации за дневные +108 природа выдала ночью грозу и ливень примерно с 1:10 до 1:30. Молнии били примерно в километре от нас, но…

  • State of disaster

    Thursday, June 25, 5:30 PM, Delay in delivery due to weather or natural disaster Wednesday, June 24, 6:16 PM, Delay in delivery due to weather or…

  • 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

  • Культурологическое

    3, 4, 6 симметрия в живой природе тоже есть, оттуда всё эти звезды и взяты? На фото – мандарин.

  • Природу, мать вашу

    В качестве компенсации за дневные +108 природа выдала ночью грозу и ливень примерно с 1:10 до 1:30. Молнии били примерно в километре от нас, но…

  • State of disaster

    Thursday, June 25, 5:30 PM, Delay in delivery due to weather or natural disaster Wednesday, June 24, 6:16 PM, Delay in delivery due to weather or…