Как повысить эффективность Алгоритма? - PullRequest
Новая
       14

Как повысить эффективность Алгоритма?

0 голосов
/ 14 июня 2019

Мне нужно поменять числа в массиве «d» раз, чтобы можно было выполнить вращение массива влево.«d» - количество вращений массива.Предположим, что если массив 1-> 2-> 3-> 4-> 5 и если d = 1, то после одного поворота влево массив будет 2-> 3-> 4-> 5-> 1.

Я использовал следующий код для выполнения вышеуказанной операции: 

for (int rotation = 0; rotation < d; rotation++) {
    for (int i = 1; i < a.length; i++) {

        int bucket = a[i - 1];
        a[i - 1] = a[i];
        a[i] = bucket;

    }
}

Но эффективность этого алгоритма слишком высока, вероятно, O (n ^ d) в худшем случае.Как повысить эффективность алгоритма, особенно в худшем случае?

Я ищу рекурсивный подход для этого алгоритма.Я придумал: 


    public static void swapIt(int[] array, int rotations){


        for(int i=1; i<array.length; i++){
            int bucket = array[i-1];
            array[i-1] = array[i];
            array[i] = bucket;  
        }

          rotations--;  

        if(rotations>0){
            swapIt(array,rotations); 
        }

        else{

            for(int i=0; i<array.length; i++){
            System.out.print(array[i]+" "); 

            }

        }

    }

Этот рекурсивный алгоритм работал, но опять-таки проблема в эффективности.Не может использовать его для больших массивов.

Ответы [ 2 ]

3 голосов
/ 14 июня 2019

Сложность вашего алгоритма для меня выглядит как O (n * d) .

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

Вы можете рассчитать назначение элемента следующим образом:

Так что вместо a[i - 1] = a[i]; Вы бы сделали это: 

a[(i + a.length - d) % a.length] = a[i];

Термин (i + a.length - d) % a.length обрабатывает то, что вы всегда получаете значения в интервале: 0... a.length-1

Пояснение:

i + a.length - d всегда положительно (до тех пор, пока d <= a.length) но оно может быть больше / равно <code>a.length, что не допускается. Так что возьмите напоминание о делении с a.length.

Таким образом, вы получаете за каждую i= 0.. a.length-1 правильную новую позицию.

Как упомянуто Satyarth Agrahari : Если d> n, вам нужно уменьшить d. d= d % a.length, чтобы убедиться, что (i + a.length - d) % a.length находится в требуемом интервале 0... a.length-1. Результат тот же, потому что вращение на a.length похоже на бездействие вообще.

1 голос
/ 14 июня 2019

чтобы добавить к ответу @ mrsmith42, вам, вероятно, следует проверить, что d лежит в диапазоне 1 <= d <= N-1.Вы можете урезать его, взяв по модулю d = d % N

...