Сложность времени при обращении строки C++

Question

У меня есть проблема с моей домашней работой, чтобы отменить слова в строке C++, вместо этого, только с O (1) дополнительной памятью. Я смущен тем, что это означает O (1) дополнительную память. Я понимаю, что вообще означает O (1), где независимо от того, насколько велик вход, время для вычисления будет постоянным, поэтому я предполагаю, что я должен добавить только одну часть памяти, которая будет отслеживать слова в обратном порядке. Какие-либо предложения?

Answer 1

O (1) дополнительная память означает «использование не более постоянной дополнительной памяти». Например, вы не смогли сохранить копию строки, так как это заняло бы пространство O (n), но вы могли бы сохранить любое постоянное число дополнительных int s, char s и т. Д.

В более общем плане - заявления типа «O (1)» или «O (n)» необязательно относятся к времени выполнения. Обозначение Big-O - это способ описания функций. Алгоритм не может быть O (n), но его время выполнения может быть O (n). Использование пространства алгоритмов аналогично может быть O (1), O (n), O (2 ⁿ) и т. Д.

Надеюсь, это поможет!