Асимптотическая сложность печати
Предполагая, что я печатаю строку, следующим образом:
printf("%s", s);
Что мы можем считать асимптотической сложностью этой функции?
Это На) где п StrLen (ы) — это длина? Или это как-то O (1), постоянное время Или что-то другое? Однако я предположил, что вам нужно знать, как printf имеет тенденцию реализовываться. Любое понимание приветствуется!
(Я должен уточнить, что я говорю о C, а не C ++, но я сомневаюсь, что они реализованы по-другому)
Редактировать: добавлена строка форматирования в printf ()
Решение
Его сложность равна O (m + n), где m — это размер входных данных, а n — размер выходных данных.
Если не передать дополнительные параметры, как в вашем случае сложность времени O (2 * m) = O (m).
Но имейте в виду, что ваш код может потерпеть неудачу, потому что s может содержать сами коды форматирования, и это приведет к неопределенному / неизвестному / непредсказуемому / возможному_в_баду результату, как указано Adriano.
Другие решения
Других решений пока нет …