Трехсторонняя и двухсторонняя сортировка без потери общности?

Question

Итак, я изучаю трехстороннюю сортировку слиянием и задаюсь вопросом о без потери общности.

Давайте предположим, что у нас есть массив A 'со степенью 3 элемента и A со степенью любой константы,

Вот мой вопрос.

1. Почему предположение о том, что n (число элементов) является степенью трех, без потери общности?

2. Почему любое предположение о том, что n является степенью константы, также без потери общности?

Answer 1

Поскольку вы всегда можете увеличить массив A, чтобы он соответствовал размеру, который вы хотите просто для того, чтобы заставить алгоритм работать.

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