denis-1921 авг 2023 в 06:23

FreeBSD переходит с сортировки пузырьком в SYSINIT на сортировку слиянием, которая примерно в 100 раз быстрее

1 мин

4.7K

Настройка Linux * Open source * Алгоритмы * Linux * История IT

Комментарии 3

easimonenko 21 авг 2023 в 20:59

20 августа 2023 года мейнтейнер FreeBSD Колин Персиваль (Colin Percival) объявил, что проект FreeBSD переходит с сортировки пузырьком в SYSINIT на сортировку слиянием, которая примерно в 100 раз быстрее.

Т.е. что значит в 100 раз быстрее? Сколько не вчитывался, сколько не ходил во Вашим ссылкам, никаких утверждений и доказательств не увидел. Откуда Вы это взяли? Прошу Proof Link!

К сведению: у Buble Sort сложность O(n^2) , а у Merge Sort $O(n \cdot \log n)$ . Где тут "быстрее в 100 раз"?

plotz 22 авг 2023 в 01:56

При n>200 (примерно) будет разница в 100 раз.

AndrewFilinsky 22 авг 2023 в 16:11

Очевидно, что при достаточно большом n разница в производительности сортировки будет больше в сколько угодно раз, и чем больше n, тем больше разница. Поэтому заявление о "примерно в 100 раз быстрее" является профанацией. Имеет смысл быть аккуратнее с формулировками.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий