Преобразовать строку в число и наоборот сложность

Question

Какова будет сложность преобразования строки в ее эквивалентное число или наоборот?Меняется ли это в зависимости от языка программирования?

На первый взгляд, нужно перебрать всю строку, чтобы преобразовать ее в число, так что это O (n) , или используется какая-то типизация?

Это сомнение возникло, когда я писал процедуру, чтобы проверить, является ли данное число палиндромом или нет.Один из подходов состоит в том, чтобы продолжать делить число на основание (здесь 10), накапливать цифры и соединять их в конце.Пример: 309/10 = rem (9), 30/10 = rem (0), 3/10 = rem (3).мы получаем 903.

Другой подход, который я выбрал, заключался в преобразовании этого числа в строку, и, поскольку в строках есть множество функций-членов для разделения, обращения и т. д., код был намного короче и чище, нолучший способ сделать это?

Answer 1

Числовые строки - это числа, отформатированные в позиционной нотации, поэтому необходимо учитывать значение каждой цифры, умноженное на степень основания, чтобы преобразовать число в двоичный формат.

Так что да, это операция O (N), потому что время работы линейно увеличивается с добавлением большего количества цифр. Однако на практике N может быть ограничено любыми числовыми типами данных, которые поддерживает язык (например, int32_t, int64_t). Но если используются типы чисел произвольной точности (которые в некоторых языках, например, Python, используются по умолчанию), то количество цифр не ограничено (очевидно, кроме доступной памяти).

Answer 2

Чтобы преобразовать в число, вы всегда должны прочитать все цифры. Так что это как минимум O(n).

Теперь делаем что-то вроде (псевдокод)

a = 0
foreach digit in string
do
   a = 10 * a + digit
end

Есть O(n). Таким образом, сложность составляет O(n)

Answer 3

Если вы конвертируете число N в строку.Требуется O (log (N)) с основанием 10. (Если вы делите на 10 и оставляете остаток) Если вы конвертируете строку с длиной N, то это занимает O (N).(Если вы используете алгоритм, который добавляет к вашему номеру 10 ^ (N) * цифру (N))

Если вы используете функции, которые не являются вашими (скажем, для строки), вы можете ожидать толькобудь медленнее.

Answer 4

Я вполне уверен, что работа с чисто числовыми операторами (в c ++ и c #, я думаю, это будет оператор модуля "%") будет более эффективной, если кодируется правильно, потому что на каком-то уровне вы должны проверять подобныефункции (совпадает ли конец с началом) и выполнение преобразования между строкой и числом может только увеличить сложность операции, если вы можете сделать то же самое без выполнения этого преобразования.

При этом я бы не сталбеспокоиться о влиянии на производительность преобразования между числами и строками, потому что оно, вероятно, незначительно по сравнению с влиянием на производительность большинства других областей программы.Числовые типы ограничены 64 битами, что ограничивает количество цифр, которые вы в любом случае планируете анализировать, если только вы не используете / не используете настраиваемые типы больших чисел.

Вы не делаетенадо беспокоиться о сложности, поскольку O (n) где n - это величина числа.Это было бы больше похоже на O (n), где n - это число цифр (с упомянутой мною нижней заглавной буквой) или (как упомянуто в другом ответе) O (log (n)), если n - это величина числа.Относительно незначительное влияние на производительность.

Теперь, если, как вы предлагаете, у вас нет ограничения на N (что невозможно, поскольку с 2 ГБ ОЗУ вы можете хранить только цифры до 2 миллиардов цифр), тогда мыВозможно, придется больше думать о производительности выполнения математических операторов.Рассмотрим производительность операторов «%» и «/» для этого типа с большим числом.Но потом поймите, что для преобразования числа в строку в любом случае используются те же самые операторы.Еще раз, вы не можете превзойти обработку его как числа напрямую, если вы все сделаете правильно.

Answer 5

C # и C / C ++ не содержат никакой специальной информации в строках, которая представляет (возможное) числовое значение.Поэтому при преобразовании им нужно анализировать строку цифра за цифрой.

Однако количество цифр ограничено, поэтому у нас есть только O (1): время преобразования ограничено (обычно путем преобразованиясамое большое количество).Для 32-разрядного типа int преобразование должно учитывать максимум 10 десятичных цифр (и, возможно, знак).

Преобразование из строки на самом деле также равно O (1), потому что во время синтаксического анализа этого достаточнорассматривать только ограниченное количество символов (10 + 1 в случае 32-разрядного типа int).

Строго говоря, мы не можем использовать O -обозначение для случая преобразования строки в строку, посколькумаксимальное значение int ограничено.В любом случае, время, необходимое для преобразования (в обоих направлениях), ограничено константой.

Как предполагает @Charles, другие языки (Python) фактически могут использовать числа произвольной точности.Для разбора таких чисел время равно O(number of digits), что O(string length) и O(log(number)) для обоих преобразований соответственно.С числами произвольной точности нельзя сделать это быстрее, поскольку для обоих преобразований должна учитываться каждая цифра.Для преобразования в / из чисел с ограниченной точностью применяется та же логика O(1).Однако я не профилировал синтаксический анализ в Python, поэтому, возможно, там используется менее эффективный алгоритм.

---

РЕДАКТИРОВАТЬ: следуя предложению @Steve, я проверил, что синтаксический анализ в C / C ++ и C # пропускаетначальный пробел, поэтому время для преобразования string-> int на самом деле O(input length).Если известно, что строка обрезана, преобразование снова O(1).