Повтор символа n раз
Даны символ и натуральное число
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-интервью
