Какова пространственная сложность сортировки битов? Согласно наилучшему и среднему случаю это O (n). Мне интересно, какова его космическая сложность
Название источника: Битовая сортировка: новая техника сортировки
Исследование IEEE сосредоточено только на временной сложности.
Спасибо!
Это O(n), поскольку вы не создаете никаких новых элементов в функции какой-либо переменной. Просто проверяя его представления битов и меняя позиции. Итак, в основном, на этих этапах:
Step 1: convert all elements into binary form but converted elements are in same BIT
sequence form.
Step 2: find elements whose first leftmost bit is 1
Step 3: repeat step 2 to all selected elements until get single BIT sequence number
Step 4: swap selected BIT sequence with last element of an array
Step 5: repeat step2, step3 and step4 until all elements are sorted
Step 6: convert sorted BIT sequence elements into decimal number
теоретически у вас нет новых элементов, когда у вас есть прямой доступ к битовым значениям заданных элементов.
Однако, если вы реализуете с точки зрения создания глубоких копий заданных элементов в их битовых представлениях, а затем снова конвертируете обратно в элементы, это все еще O(n) (просто 3*n). Теперь при обмене с глубокой копией элементов вам все еще нужно до n новых пространств памяти (n — это когда вы всегда занимаете новое пространство в памяти при обмене). В лучшем случае при обмене с глубокой копией вам понадобится только одно пространство памяти. То же самое касается замены указателя. В целом, это O(n).
