Здравствуйте, CoderMonkey, Вы писали:
CM>2. Отсортировать массив, не сравнив каждый элемент с каким-либо другим как минимум раз — невозможно.
Люди, писавшие сортировку подсчетом, смотрят на вас с недоумением
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>о, пошли философские разговоры. Люблю такое. Что такое "О-фактор", расскажИте? А то у меня тут общепринятое понимание — оно про время выполнения и про дополнительную память
CM>Общепринятое понимание — про число операций и память.
Серьезно?
Since this function is generally difficult to compute exactly, and the running time for small inputs is usually not consequential, one commonly focuses on the behavior of the complexity when the input size increases—that is, the asymptotic behavior of the complexity. Therefore, the time complexity is commonly expressed using big O notation, typically {\displaystyle O(n),} O(n), {\displaystyle O(n\log n),} {\displaystyle O(n\log n),} {\displaystyle O(n^{\alpha }),} {\displaystyle O(n^{\alpha }),} {\displaystyle O(2^{n}),} {\displaystyle O(2^{n}),} etc., where n is the input size in units of bits needed to represent the input.
ylp>>гениально, браво, спасибо. КО! Если сравнивать элементы массива не по два за один шаг алгоритма, а параллельно группами, можно успеть сделать сравнения быстрее, улавливаете?
CM>И вместо C1 * O(N) ты получишь C2 * O(N), где C2 < C1 CM>Улавливаешь?
Я вижу, что no hire на скринге сделан был совершенно обосновано. Плавать в таких вещах как вычислительная сложность алгоритмов и упорно продолжать при этом спорить, когда перед глазами есть весь интернет — это весьма сильно.
ylp>>я смотрю, вам нравится выставлять себя идиотом. продолжим: https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort CM>Объясняю на пальцах, для самых тупых. Бесконечно больших сортирующих сетей — не бывает.
Radix sort сортирует только числа небесконечной разрядности.
Деда Мороза не существует. Вам напомнить, с чего начался наш разговор?
Здравствуйте, ylp, Вы писали:
ylp>У вас серьезные проблемы с пониманием big-O notation. Раз вам так нравится, я еще раз дам ссылку на википедию и цитату оттуда.
Та же википедия:
Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n log n) comparisons to sort n items.
Обращаю внимание, для однопоточного выполнения, число операций = время. Однако, если для однопоточных алгоритмов обычно фигурирует time или operations, то для параллельных — parallel time.
Сравниваем метры с килограммами, ага?
CM>>И вместо C1 * O(N) ты получишь C2 * O(N), где C2 < C1 ylp>Я вижу, что no hire на скринге сделан был совершенно обосновано. Плавать в таких вещах как вычислительная сложность алгоритмов и упорно продолжать при этом спорить, когда перед глазами есть весь интернет — это весьма сильно.
Оспорить утверждение выше ты в состоянии?
ylp>Radix sort сортирует только числа небесконечной разрядности. ylp>Деда Мороза не существует. Вам напомнить, с чего начался наш разговор?
Значит, не дошло. Объясняю еще более на пальцах. Чем больший массив тебе нужно отсортировать, тем больше растет размер сортирующей сети, который для этого нужен. Причем растет быстро. И это значит, что очень быстро ты упрешься в потолок, выше которого поднять размер сети просто невозможно, и тебе придется разбивать массив на части, сортировать их по отдельности, а потом делать слияние. И вот последний необходимый шаг требует O(N) и никак не быстрее.
Достаточно доступно, или нужно объяснить еще подробнее?
Здравствуйте, CoderMonkey, Вы писали:
CM>Имел собеседование со "специалистом" из Гугла. На вопрос "какова лучшая сложность для алгоритмов сортировки", ответил ему, что O(n). Нет, говорит, это неправильно — должно быть O(n * log n). Правильно, говорю, именно O(n). Есть такой radix sort, у него сложность именно такая. В ответ — недоуменно-возмущенное молчание. Похоже, не поверил. CM>Кажется, никакое продолжение мне не светит :))
Гугл — есть гугл. Компания крутая, как по продуктам, так и по ЗП. Поэтому они отбирают лучших.
Ну как бы Radix Sort работает только для целых положительных чисел. Поэтому надо было либо уточнить вопрос: А какие данные сортировать хотите? А если уж хотел сверкнуть знаниями, то так и надо было говорить: radix sort для uint c O(n), quick sort & merge sort с O(n * log n).
Здравствуйте, white_znake, Вы писали:
_>Ну как бы Radix Sort работает только для целых положительных чисел.
Тут есть такой нюанс — на компьютере, абсолютно любые данные представляют собой набор байтов. То есть — положительных целых чисел. Странно, что так много программистов этого не понимают.
Здравствуйте, CoderMonkey, Вы писали:
_>>Ну как бы Radix Sort работает только для целых положительных чисел. CM>Тут есть такой нюанс — на компьютере, абсолютно любые данные представляют собой набор байтов. То есть — положительных целых чисел. Странно, что так много программистов этого не понимают.
Но порядок сортировки может не соответствовать порядку битового представления.
Здравствуйте, B0FEE664, Вы писали:
BFE>Но порядок сортировки может не соответствовать порядку битового представления.
Данные можешь представить алгоритму в любой форме, которая тебе нужна. Не намного сложнее, чем написать компаратор для классов (хотя, конечно, и с этим многие не справляются)
int GetDigit(SomeClass field, int index)
{
if (blahblahblah)
return something;
// ......
}
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>Облажался — прикинься философом, ага.
CM>Ага, это ты умеешь. Отсортируй ка мне массив объектов подсчетом.
Ой, баоюс-баюс!
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, ylp, Вы писали:
ylp>>У вас серьезные проблемы с пониманием big-O notation. Раз вам так нравится, я еще раз дам ссылку на википедию и цитату оттуда.
CM>Обращаю внимание, для однопоточного выполнения, число операций = время.
Число операций не = время, а пропорционально времени. И да, спасибо, КО! > Однако, если для однопоточных алгоритмов обычно фигурирует time или operations, то для параллельных — parallel time. CM>Сравниваем метры с килограммами, ага?
Сравнивается время выполнения одних алгоритмов со временем выполнения других алгоритмов. В случае с последовательными алгоритмов время пропорционально числу операций, в случае паралельных — нет. Big-O notation как мы уже выяснили, она про время, а не про число операций.
CM>>>И вместо C1 * O(N) ты получишь C2 * O(N), где C2 < C1 ylp>>Я вижу, что no hire на скринге сделан был совершенно обосновано. Плавать в таких вещах как вычислительная сложность алгоритмов и упорно продолжать при этом спорить, когда перед глазами есть весь интернет — это весьма сильно. CM>Оспорить утверждение выше ты в состоянии?
Зачем оспаривать бред людей, которые базовых вещей не понимают. Это скучно. Интереснее вас просто троллить.
ylp>>Radix sort сортирует только числа небесконечной разрядности. ylp>>Деда Мороза не существует. Вам напомнить, с чего начался наш разговор?
CM>Значит, не дошло. Объясняю еще более на пальцах. Чем больший массив тебе нужно отсортировать, тем больше растет размер сортирующей сети, который для этого нужен.
Офигеть, продолжайте.
>Причем растет быстро.
Круто!
>И это значит, что очень быстро ты упрешься в потолок
Нифига себе! Потолок чего?
> выше которого поднять размер сети просто невозможно, и тебе придется разбивать массив на части
Не, уже скучно, повторяетесь.
CM>Достаточно доступно, или нужно объяснить еще подробнее?
Не, не нужно. пойдите в википедию и почитайте, чему пропорционален размер сортирующей сети, которая сортирует массив длины N за O(log^2(N)).
Давайте я, как обычно, вам помогу найти нужное место в тексте, которое вы не видите:
Здравствуйте, CoderMonkey, Вы писали:
BFE>>Но порядок сортировки может не соответствовать порядку битового представления. CM>Данные можешь представить алгоритму в любой форме, которая тебе нужна. Не намного сложнее, чем написать компаратор для классов (хотя, конечно, и с этим многие не справляются)
Не намного сложнее? Напишите для строк неизвестной длины.
Ага.
Задание для не совсем тупых: оценить количество операций сравнения символов в алгоритме, который указаным вами способом сортирует массив строк, длина каждой из которой равна размеру массива. Сравнить с квиксортом, много думать (надуюсь, у вас получится!).
Здравствуйте, ylp, Вы писали:
ylp>Big-O notation как мы уже выяснили, она про время, а не про число операций.
Тебе никогда не приходило в голову — а почему в Big-O notation фигурирует название сложность алгоритма, а не "скорость" или "время выполнения"?
CM>>>>И вместо C1 * O(N) ты получишь C2 * O(N), где C2 < C1 ylp>Зачем оспаривать бред людей, которые базовых вещей не понимают. Это скучно. Интереснее вас просто троллить.
Еще раз. Ты в состоянии оспорить утверждение выше, или будешь и дальше устраивать истерику?
ylp>Повторяю для особо одаренных: размер сортирующей сети пропорционален n*log^2(n).
А теперь посчитай, какой размер сети тебе понадобится для массива в, хотя бы, 1 миллион элементов. Я уверен, ты сможешь справиться с этой не слишком сложной математикой.
Здравствуйте, ylp, Вы писали:
ylp>Ага. ylp>Задание для не совсем тупых: оценить количество операций сравнения символов в алгоритме, который указаным вами способом сортирует массив строк, длина каждой из которой равна размеру массива. Сравнить с квиксортом, много думать (надуюсь, у вас получится!).
Даю намек. Попробуй оценить количество операций сравнения символов в алгоритме QuickSort, который сортирует массив строк, длина каждой из которой равна размеру массива.
Это совсем не сложно, должно получиться даже у тебя.
