170 похожих чатов

Что там, изобретаем сортировку с линейной сложностью?

8 ответов

5 просмотров

А сложность линейной не будет

evle
Откуда такая уверенность?

Ну потому что мы получаем данные за линейную сложность, а потом работает с полученными данными много времени

Илья Власов
Ну потому что мы получаем данные за линейную сложн...

Что мешает "много времени" так же быть линейным? Я пока до конца не додумал, но явных ограничений, почему нельзя за линейное время — не вижу.

Ну если сталин сорт и подобное не брать

Илья Власов
Ну если сталин сорт и подобное не брать

Не только. Теоретический предел в nlogn — у сортировок сравнениями. То есть когда единственная доступная нам информация для принятия решения — результат сравнения двух элементов массива. Всякие bucket sort и подобные имеют другую асимптотику при определённых ограничениях на входные данные. А у нас данные сильно ограничены.

evle
Не только. Теоретический предел в nlogn — у сортир...

Соглашусь, я перечитал условие и понял, что тут на это и делался жирный намек, а я даже чет и не заметил

evle
Не только. Теоретический предел в nlogn — у сортир...

Блин, реально, тут же конкретно прям блочная сортировка идеально встает

Похожие вопросы

Обсуждают сегодня

Добрый день. Хочу сделать отрисовку по команде на панели. Почему-то рисуется только при втором вызове. С чем может быть связано, не подскажете? procedure TForm1.FormDblClick(...
Kirill Filippenok
20
а зачем этот вопрос для удаления из чата?
Mёdkinson Medvezhkin
63
А почему в си некоторые вещи работают с двойными кавычками некоторые с одинарными? Нельзя было все сделать с одними или чтоб работало с разными? например чтоб выводить строки ...
.
15
Всем привет! Нужен совет от опытных. Переношу свой проект с Делфи 10.2 Токио на Лазарус 3.2 установленный через инсталлятор fpcupdeluxe-x86_64-win64. При импортировании проект...
Дмитрий Завгородний
7
Всем привет! procedure TForm1.FormCreate(Sender: TObject); type TStartEnd = record S: Byte; E: Byte; end; var a, b: TStartEnd; begin {1} a.S := 1; {2} a.E := 2; ...
Руслан Михайлович
10
Всем привет!) я тут новенький и пытаюсь освоить evolution методом тыка. У меня при переходе между папками файлов выскакивают вот такие уведомления Можете подсказать как их от...
Диман Samoed
10
Эх кто-то пришел и весь праздник испортил :( You need complex FBX scene importing setup to change things on import? good luck with that. You need navigation and pathfinding? g...
Serg Gini
5
Всем привет! Подскажите. Я написал приложение на Delphi 10.2 Tokyo под Windows 10. И передо мной стал вопрос о том чтобы сделать это приложение кроссплатформенным (под Linux и...
Дмитрий Завгородний
24
Какого хера? /Sources/App/Modules/User/Models/UserLinkApple.swift:21:20: warning: stored property '_id' of 'Sendable'-conforming class 'UserLinkApple' is mutable @ID(...
Alexander Sherbakov
14
Привет всем. Подскажите где можно посмотреть, какая версия электрон, поддерживает версии windows? Некий changelog. Мне бы желательно, поддержку 7,8,10... latest, как понимаю и...
Anonym Squad
21
Карта сайта