如何提高算法的效率？

Question

我必须交换数组中的数字 '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]+" "); 

            }

        }

    }

此递归算法有效，但效率再次成为问题。不能将它用于更大的阵列。

Answer 1

你的算法的复杂性对我来说看起来像 O(n*d)。

我的做法不是旋转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）但它可能 greater/equal 而不是 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 就像什么都不做。

Answer 2

添加 @mrsmith42 的答案，您可能应该检查 d 是否在 1 <= d <= N-1 范围内。你可以 trim 取模为 d = d % N

如何提高算法的效率？

How to improve efficiency of the Algorithm?

algorithm

recursion

swap