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

Viktor Karpov
Jul 29, 2017 · 2 min read

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

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

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

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

Единственное, что нужно учесть — это хвост, его нужно добавить отдельно.

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

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

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

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

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

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

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


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

Viktor Karpov

Written by

Software engineer. Алгоритмы, JavaScript. https://github.com/vitkarpov

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade