Повтор символа n раз

Даны символ и натуральное число n. Нужно вывести строку длины n , состоящую из этого символа.

Наивный подход — сложить символ в пустую строку n раз. Сложность линейная.

Можно ли сделать быстрее, чем за O(n) ? Можно за O(log n) .

Суть в том, чтобы складывать строку саму с собой, таким образом увеличивая её размер в 2 раза, а количество операций — уменьшая в 2 раза, отсюда логарифмическая сложность.

Единственное, что нужно учесть — это хвост, который может остаться от n после log(n) операций, его нужно добавить отдельно.

Функция возвращает строку указанной длины, повторяя указанный символ.

Отдельный вопрос с тем как это сделать, с точки зрения сложности. В принципе, можно воспользоваться String.prototype.substr , но надо оценить его сложность.

Для интереса, я заглянул в реализацию JavaScript строки в V8. Результат ожидаемый: substr , substring , slice , в конечном итоге, «проксируются» в substr строки из стандартной библиотеки C++ std::basic_string , если точнее.

Стандарт C++ не накладывает никаких ограничений на сложность substr , поэтому все зависит от реализации.

По крайней мере, вGCC к любому элементу можно получить доступ за константное время, т.е. любой кусок можно достать из любого места строки за одно и то же время, но потребуется время чтобы скопировать указанное количество символов в новую строку.

Вообще говоря, придется предполагать, что сложность линейная, однако важно, что она линейная относительно длины, указанной для substr , а не исходной строки, из которой вырезаем кусок.

Если посмотреть на возможную длину хвоста, то он ограничен сверху — не может быть больше log (n) , соответственно, substr даст прибавку не более чем в log(n) времени.

Таким образом, итоговая сложность равна 2 * log(n) = O(log n) .


Это реальная задача, которую я получил на одном из screen-интервью