Время выполнения для массива с элементами разного размера

Question

Например, для массива A [1, ..., n] мы предполагаем, что все элементы имеют одинаковый размер.Затем итерация по массиву занимает O (n) времени.Что, если размер элементов отличается (все еще ограничен)?Как это влияет на время работы?

Спасибо

Answer 1

Это большой теоретический вопрос.Есть три ответа.

1. Практически, размер числа почти никогда не влияет на время выполнения.На практике все числа в массиве кодируются с использованием одинакового количества битов.Если вы используете int32, он будет 32-битным;если int16, 16 бит;и так далее.Для числа 1, закодированного в int32, требуется столько же битов (32), сколько для огромного числа 2 ^ 31, закодированного в int32.
2. Теоретически размер числа абсолютно влияет на время выполнения.Например, если размер элемента в массиве был 10 ^ 2000, любой алгоритм, работающий с этим массивом, должен был бы работать дольше, чем возраст юниверса, только чтобы прочитать этот элемент.
3. Интересным примером является сортировка по осям, где размер числа влияет на время выполнения, а не только теоретически.Корневая сортировка - это тип алгоритма сортировки, время выполнения которого равно O (nK), где n - это количество элементов в массиве, а K пропорционально числу битов, необходимых для представления каждого элемента массива.Таким образом, радикальная сортировка массива объектов int32 потребует примерно вдвое больше времени выполнения, чем радикальная сортировка массива объектов int16.

Answer 2

Поскольку вы еще не описали свою парадигму сравнения, мы не можем ответить наверняка.Тем не менее, ваша ссылка на пузырьковая сортировка предполагает, что ваши элементы представляют собой простые числовые скалярные значения по сравнению с общими определениями порядка.

Как правило, время выполнения затрагивается: сравнение 1024-битных значений с 32-битными значениями может занять до 32 раз.Однако эти издержки являются просто постоянным коэффициентом: алгоритмическая сложность все еще O (N ^ 2) .Сортировка пузырьков все еще будет завершена после (N)*(N-1)/2 сравнений, каждое из которых имеет фиксированную конечную верхнюю границу.

Один простой способ предположить это - предварительно обработать все элементы массива до размерапо величине.В упомянутом числовом случае вы заполняете каждый элемент нулями до 1024 бит.Теперь все элементы имеют одинаковый размер, и мы уменьшили проблему до того, что было ранее решено.