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

Question

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

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

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

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

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

Answer 1

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

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