Как использование строк вместо простых типов, таких как целые числа, может изменить О-нотацию операций?

Question

Предложенный ответ:

Строки - это просто массивы символов, поэтому обозначение O будет зависеть от количества символов в строке (если цикл зависит от длины строки). В этом случае обозначение O не будет затронуто, потому что длина строки равна константе.

Есть еще идеи? Я правильно читаю этот вопрос?

Answer 1

Это не так, поскольку представление целых чисел в массивах не безгранично.

IOW строка, представляющая 32-разрядное целое число, максимально 32-разрядная, то есть максимально 10 цифр в базе 10, а O (10) - это отрицательная константа, которая не меняет обозначение O.

Итак, в итоге, хотя строки O (n), основные целочисленные типы, представленные в виде строк, O (максимально 10) = O (0)

Я думаю, вам нужно лучше указать свою проблему.

Answer 2

Попробуйте подумать о чем-то, что работает с массивом целых чисел или массивом строк, ясно, что в последнем случае у вас есть массив массива примитивного типа, а не массив примитивного типа. Как это меняет вещи?

Answer 3

Это полностью зависит от того, что вы делаете со строками.

Если вы, например, копируете элементы из одного массива в другой, результат зависит от реализации. Это все еще операция O (n), но значение n меняется. Если при копировании строки создается новая копия, n означает общее количество символов во всех строках. Если при копировании строки копируется только ссылка на нее, n означает общее количество строк.