объединение и сортировка 2 отсортированных массивов с большим o ищет уточнения.

Question

Это школьная работа.Я не ищу помощи по коду, но поскольку мой учитель не помогает, я пришел сюда.

Меня просят объединить и отсортировать два отсортированных массива в следующих двух случаях:

1. Когда размерыиз двух массивов равны
2. Когда размеры двух массивов различны

Теперь я сделал случай 2, который также делает случай 1: / Я просто не понимаю, какЯ мог бы написать код для случая 1 или как он может отличаться от случая 2. Длина массива не связана с проблемой, или я не правильно понимаю.

Затем меня просят вычислить big (o).

Я не ищу здесь код.Если кто-нибудь случайно поймет, о чем действительно просит мой учитель, пожалуйста, дайте мне подсказки, чтобы решить его.

Answer 1

Объединение двух отсортированных массивов является операцией линейной сложности.Это означает, что с точки зрения записи Big-O это O (m + n), где m и n - длины двух отсортированных массивов.

Так что, когда вы говорите array length doesn't connect with the problem, ваше понимание верно.Независимо от длины двух отсортированных массивов объединение этих массивов включает в себя извлечение элементов из каждого отсортированного массива и сравнение их и копирование одного в новый массив (в зависимости от того, требуется ли объединенный отсортированный массив в порядке возрастания или убывания) и увеличение счетчикамассив, из которого вы скопировали элемент в новый отсортированный массив.

Answer 2

Еще один способ подойти к этому вопросу - посмотреть на каждый массив как имеющий голову и хвост и рекурсивное решение проблемы.Таким образом, мы можем использовать базовый вариант, два массива размером 1, чтобы отсортировать все два массива m и n.Поскольку оба массива уже отсортированы, просто сравните две головки каждого массива и добавьте элемент, который находится первым в вашем вновь созданном объединенном массиве, и перейдите к следующему элементу в этом массиве.Ваша функция снова вызовет себя после добавления элемента.Это будет происходить до тех пор, пока один из двух массивов не опустеет.Теперь вы можете просто добавить то, что осталось от непустого массива, в конец вашего объединенного массива, и все готово.

Я не уверен, позволит ли ваш профессор вам использовать рекурсивные вызовы, но этометод может сделать кодирование намного проще.Время выполнения все равно будет равно O (m + n), поскольку вы в основном выполняете итерацию по обоим массивам один раз.

Надеюсь, это поможет.

Answer 3

Очень хорошо учиться, а не копировать.
Как вы предполагаете, нет разницы между вариантами 1 и 2, но наихудший вариант алгоритмов зависит от вашего решения.Поэтому я опишу свое решение (без кода) и дам вам его худший случай.
В обоих случаях массивы должны заканчиваться бесконечностью, поэтому добавьте к ним бесконечность.затем итерируйте по всем элементам каждого массива, в каждый момент времени выбирайте тот, который меньше, и вставляйте его в свой массив результатов (объединение массивов буксировки).
С этим решением вы можете легко вычислить наихудший случай.мы должны перебрать оба массива один раз, и мы добавим бесконечность к ним обоим, если их длина равна n и m, поэтому наш худший и лучший случай - O(m + n) (вы делаете m + n + 2 - 1 сравнение и -1, потому что вы этого не делаетесравните конец обоих массивов, я имею в виду бесконечность)

но зачем добавлять бесконечность добавить конец массива?потому что для этого мы должны сделать копию массива с еще одним пробелом?это один из способов, и наихудший случай - O(m + n) для копирования массивов тоже.но есть и другое решение.вы можете сравнивать, пока не доберетесь до конца массива, затем вы должны добавить остаток массива, который не сравнивается полностью с концом вашего массива результатов.но с бесконечностью, это автоматически.

Я надеюсь, что помог вам.если что-то не так, прокомментируйте это.