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


ylp>>Спасибо, КО! Вы не заметили, что теперь вы сами себе противоречите? Еще совсем недавно вы говорили про "невозможно реализовать в железе".
CM>Врешь. Мой контраргумент с самого начала, цитирую — "бесконечно большие сортирующие сети невозможны"
Ваш конрагрумент на что? Я где-то говорил, что они возможны? Я привел в пример алгоритм сортировки, работающий быстрее чем O(N).

ylp>>Но хорошо хоть что признали, что алгоритм сортировки, сортирующий быстрее, чем O(N) таки существует (хоть и применим не всегда) и согласно вашей же логике, на интервью ответ O(N) без уточнение вопроса был неверным.

CM>См выше про разницу между "сложностью алгоритма" и "скоростью алгоритма".
О, опять философские беседы, люблю такое!

В чем, в чем разница-то?
Вам уже ссылку на определение сложности алгоритма давали, где явно упоминается время выполнения, но пока что что в лоб что по лбу
давайте еще раз, раз вам так нравится:

https://en.wikipedia.org/wiki/Computational_complexity#Time

Time
The resource that is most commonly considered is the time, and one talks of time complexity. When "complexity" is used without being qualified, this generally means time complexity.

https://en.wikipedia.org/wiki/Time_complexity

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.

Теперь напрягитесь и подумайте, что значит "commonly" и что в случае с сортирующими сетями такое "elementary operation that takes a fixed amount of time to perform". Подсказка — в сортирующих сетях за один интервал времени работают параллельно несколько узлов, а не один.