от
Я вижу, что многие реализации сортировки с объединением, я вижу в интернете, таких как https://www.geeksforgeeks.org/merge-sort/ передавать аргументы L, м и R, чтобы знать, где суб массивы начала и конца. Мне было интересно, если во время выполнения и сложность пространства остаются неизменными, если вместо того, чтобы мы сделали копии из вложенных массивов и передал их в. Образец предложенный код выглядит следующим образом:
class Solution {

    //mergeSort implementation
    public int[] sortArray(int[] nums) {

        if (nums.length == 1) {
            return nums;
        }

        int arrayLength = nums.length;

        // make copies instead of passing indices
        int[] left = Arrays.copyOfRange(nums, 0, arrayLength/2);
        int[] right = Arrays.copyOfRange(nums, arrayLength/2, arrayLength);

        left = sortArray(left);
        right = sortArray(right);

        return merge(left, right);

    }

    public int[] merge(int[] left,int[] right) {

        int[] merged = new int[left.length   right.length];

        int mergedCounter = 0;
        int i = 0; //leftCounter
        int j = 0; //rightCounter
        while (mergedCounter != left.length   right.length) {
            if (i == left.length) {
                merged[mergedCounter] = right[j];
                mergedCounter  ;
                j  ;
            } else if (j == right.length) {
                merged[mergedCounter] = left[i];
                mergedCounter  ;
                i  ;
            } else {
                if (left[i] 
Я считаю, что сложность не увеличивается, потому что копия занимает столько же времени запуска инициализации N-длина нового массива через new инт[Н]. Этой части проблемы также включает в себя О(Н) слияния подфункция так что это не важно. Я тоже считаю, что сложность пространства остается неизменным. В то время как мы создаем два временных подмассивов в рекурсивном вызове, то же самое количество пространства будет создан при слиянии шаг, как указано в онлайн-решений, используя указатели на Л, М и Р. Мой мыслительный процесс действует, или я что-то пропустила?

Ваш ответ

Отображаемое имя (по желанию):
Конфиденциальность: Ваш электронный адрес будет использоваться только для отправки уведомлений.
Анти-спам проверка:
Чтобы избежать проверки в будущем, пожалуйста войдите или зарегистрируйтесь.
Добро пожаловать на сайт ByNets, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...