denis-19 Aug 21 2023 at 06:23

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

1 min

4.4K

Configuring Linux * Open source * Algorithms * Development for Linux * History of IT

Comments 3

easimonenko Aug 21 2023 at 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 Aug 22 2023 at 01:56

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

AndrewFilinsky Aug 22 2023 at 16:11

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