Здравствуйте, ylp, Вы писали:

ylp>в разделе "сортирующие сети" и "параллельные вычисления". Могу, правда, ошибаться и там будет квадрат логарифма от размера массива, а не логарифм размера массива.
ylp>Эти алгоритмы работают не сравнивая попарно элементы, а обрабатывая весь массив целиком (т.е. предполагается не стандартная фон-неймановкая архитектура, а другая модель вычислений). На практике такого полно — GPU, ASIC и т. д.


1. Если ты разобьешь алгоритм на несколько ядер или других вычислительных элементов, то количество операций от этого не уменьшится — уменьшится только время выполнения. Соответственно, величина О-фактора останется абсолютно той же.
2. Отсортировать массив, не сравнив каждый элемент с каким-либо другим как минимум раз — невозможно.
3. Размер любого ASIC или GPU ограничен, а это значит, что и логарифмического времени там тоже не будет — будет оно все равно линейным
Звон ты где-то услышал, но смысл — вообще не понял.