Big-O Memory of Array vs String

Question

Это может звучать глупо, но я подумал, подумав немного, разве вы не можете поиграть с алгоритмом и заставить O (n) память казаться O (1)?

(Java) Допустим, выиметь массив из N элементов true или false.Тогда этот массив приведет к O (n) памяти.

Однако, если у нас есть массив, скажем, «FFFFFTFTFFT» с каждым charAt (i), отвечающим на результат i-го индекса массива,Разве мы не использовали только O (1) памяти или это считается O (n) памятью, так как String имеет размер самого O (n)?

Давайте продолжим.Если у нас есть N-массив значений true и false и мы конвертируем его в байты, мы используем еще меньше памяти.Тогда считается ли байт O (1) памятью или O (n) памятью?Например, скажем, n = 6. Тогда размер массива равен 6 = O (n).Но размер байта составляет всего 1 байт, так как 1 байт может хранить 8 различных значений (8 бит).Так это O (1) или O (n), поскольку для большого N мы получаем следующий случай ...: N равно 10000. Массив - это O (n) памяти, но является ли байтом память?Потому что наш байт O (n / 8) = O (n)?

Answer 1

Все описанные вами случаи O(n), он описывает ограничивающее поведение, когда n стремится к бесконечности, математически говоря:

f(n) = O(n), as n -> INF равно f(n)/n -> const, as n -> INF, где const <> 0

Итак 10*n + 100 = O(n) и 0.1*n = O(n).

И, как вы написали, следующее утверждение также верно: O(n/8) = O(n) = O(n/const)

Answer 2

Здесь есть еще одно заблуждение: чтобы действительно создать «контейнер символов» с этим свойством O (1) (соответственно: O (log n), так как требуемая память все еще растет с ростом данных), это будет работать только для этого: строки, содержащие n символов одного вида и 1 символов другого типа.

В таких случаях да,вам нужно будет только запомнить индекс, который имеет другой символ.Это похоже на определение супер разреженной матрицы: если в огромной матрице только одно значение! = 0, вы можете хранить только соответствующие индексы вместо всей матрицы с gazillions из 0 значений.

И, конечно: есть библиотеки, которые делают такие вещи для разреженных матриц, чтобы снизить стоимость хранения известных 0 значений в памяти.Зачем что-то вспоминать, когда можно (легко) это вычислить ?!

Answer 3

Я не уверен, что вы полностью понимаете концепции Большого О, но у вас все еще есть N элементов в каждом из перечисленных случаев.

Обозначение O(N) представляет собой верхнюю границу для функции из N элементов, не столько определяемую размером базовых типов данных, сколько отмечалось O(N/8) = O(N).

Так, например,

Если у нас есть N-массив значений true и false и преобразовать его в байты

Вы преобразуете N элементов вN байт.Это O(N) сложность времени.Вы сохранили 2 * O(N) всего массивов, что привело к O(N) сложности пространства.

charAt(i)

Одна только эта операция O(1) сложность времени, потому что вы получаете доступодин элемент.Но у вас есть N элементов в массиве или строке, так что это O(N) сложность пространства

Я не совсем уверен, что существует общий O(1) алгоритм сложности пространства (за исключением простых математических операций)