flax wrote:

> ME>Это действительно не константа, но ее время исполнения можно принять за константу, так как на каждой итерации он будет выполняться за константное время (если, конечно, размер твоего массива постоянен). Только если время выполнения memset будет равно времени исполнения одной итерации (что, как мне кажется, маловероятно), memset сможет повысить степень выражения асимптоматической сложности алгоритма.

> 1) Сложность алгоритма считается в наихудшем и асимптотическая ( в O()).
> 2) Размер P-массива равен n — и n может (считаем поведение на бесконечности) быть оЧень большим

memset не работает на бесконечности

> 3) Насколько я понимаю, memset есть (буквально)"оптимизированная версия пробежать первых n байт и заполнить их фиксированным значением". Т.е. ты говоришь, что он просто очень быстрый (если n-мало), не более того.

Именно так. memset не увеличит количество итераций твоего алгоритма, лишь сделает каждую итерацию медленнее, поэтому memset не сделает из O(n * log(n)) алгоритма O(n^2) алгоритм.

--
Maxim Yegorushkin