Почему в решениях с одинаковой сложностью существенная разница во времени расчета?
Почему в решениях с одинаковой сложностью существенная разница во времени расчета?
Я отвечу на вопрос из заголовка: потому что сложность алгоритма говорит о том, как он будет вести себя при неограниченном увеличении размерностей входных данных. И больше ни о чём. Т.е. нельзя имея два линейных алгоритма сказать, что они будут работать одинаковое время. Но можно имея линейный и квадратичный алгоритм сказать, что начиная с какого-то момента линейный всегда будет работать быстрее.
Виноваты накладные расходы.
В traditional_way они минимальны.
Замените лямбды вычислением промежуточного массива содержащего abs(a-x) в остальных случаях и получите дополнительный прирост производительности.