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

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

CM>1. Если ты разобьешь алгоритм на несколько ядер или других вычислительных элементов, то количество операций от этого не уменьшится — уменьшится только время выполнения.
> Соответственно, величина О-фактора останется абсолютно той же.
о, пошли философские разговоры. Люблю такое. Что такое "О-фактор", расскажИте? А то у меня тут общепринятое понимание — оно про время выполнения и про дополнительную память

CM>2. Отсортировать массив, не сравнив каждый элемент с каким-либо другим как минимум раз — невозможно.
гениально, браво, спасибо. КО! Если сравнивать элементы массива не по два за один шаг алгоритма, а параллельно группами, можно успеть сделать сравнения быстрее, улавливаете?

CM>3. Размер любого ASIC или GPU ограничен, а это значит, что и логарифмического времени там тоже не будет — будет оно все равно линейным
CM>Звон ты где-то услышал, но смысл — вообще не понял.
я смотрю, вам нравится выставлять себя идиотом. продолжим: https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort

Worst-case performance {O(log^{2}(n))} parallel time