Предположим, что ваш первый массив называется A1 из n1 элементов, а ваш второй называется A2 из n2 элементов:
увеличивает длину A1 и добавляет к нему A2 по стоимости * 1005.*, где c является константой.Применяйте быструю сортировку и заказывайте ее по другой цене O( (n1+n2)*log(n1+n2) ).Вы упомянули, что не хотели очевидного пути, однако, вы хотели, чтобы работа была выполнена наилучшим образом.Это, вероятно, лучший способ, потому что он позволяет вам по-прежнему использовать обычные массивы, которые обычно являются самыми быстрыми структурами данных для работы в целом (конечно, это зависит конкретно от того, над какой задачей вы работаете).
Однако,другая возможность состоит в том, чтобы сделать A1 связанным списком, встроенным в обычный массив, для целей этого анализа мы не будем рассматривать затраты на преобразование A1 из обычного массива в связанный список.Следовательно, подход заключается в вставке упорядоченного каждого элемента A2 в A1.Очевидный способ вставить заказанный состоит в том, чтобы проверить каждый элемент A1 и затем решить, куда вставить, за счет O(n1 + c) для каждой вставки.Однако более разумным методом было бы выполнить бинарный поиск по A1, чтобы решить, куда следует вставлять каждый элемент A2, за счет O(log(n1) + c) для каждой вставки.В этом случае будет n2 вставок, что составляет общую стоимость n2*O(log(n1) + c).При таком подходе вам не нужно перемещать какие-либо элементы A1, так как мы предполагаем, что вы используете связанный список, все, что вам нужно, это проверить эти элементы.Вот почему эта асимптотическая функция выглядит лучше, эта структура данных дает вам возможность смотреть только на исходные элементы А1 без их фактического перемещения.
Чтобы решить, какой подход следует использовать, я рекомендую проанализировать алгоритм, который подходитпосле слияния массивов выберите вариант, который наилучшим образом соответствует вашим потребностям.