Сложность времени при обращении строки C ++
У меня проблема с домашним заданием, чтобы поменять слова в строке C ++, только с O (1) дополнительной памятью. Я смущен тем, что означает O (1) дополнительная память. Я понимаю, что обычно означает O (1), где, независимо от того, насколько велик ввод, время для вычисления будет постоянным, поэтому я предполагаю, что мне нужно добавить только один фрагмент памяти, который будет отслеживать слова в обратном порядке. Какие-либо предложения?
Решение
O (1) дополнительная память означает «использование не более некоторой постоянной дополнительной памяти». Например, вы не можете сохранить копию строки, так как это займет место O (n), но вы можете хранить любое постоянное число дополнительных ints, charс и т. д.
В более общем смысле операторы типа «O (1)» или «O (n)» не обязательно относятся к средам выполнения. Нотация Big-O — это способ описания функций. Алгоритм не может быть O (n), но его время выполнения может быть O (n). Использование пространства алгоритмом аналогично может быть O (1), O (n), O (2).N), так далее.
Надеюсь это поможет!
Другие решения
Других решений пока нет …
detector