数组的交换算法O（N）（Java） [英] Swap algorithm for arrays O(N) (Java)

问题描述

各位大家好！



我想就我正在做的一个交换算法问一些帮助。该算法需要将数组的所有元素与其元素的每个可能组合交换。我试图为这个算法获得尽可能最好的时间复杂度，但我不能做得比O好（N加到2）。我的想法已经不多了。我的算法如下：



代码：

Hello everybody!

I would like to ask some help regarding one swap algorithm I am doing. The algorithm need to swap all elements of the array with every possible combination of the elements of it. I am stuck trying to get the best possible time complexity for this algorithm, but I cannot do better than O(N raised to 2). I am running out of ideas. The algorithm I have is the following:

Code:

import java.math.*;


class SwapAlgo {
    public int main(int[] A) {
        int l=0,k=0;
        


            //Swap algorithm
            for (l=0 ; l < A.length ; l++){
                for (k = l+1 ; k < A.length ; k++){


                    int [] A_aux = A;
                    int num_aux = A_aux[l];
                    A_aux [l] = A_aux[k];
                    A_aux[k]=num_aux;
                    
             }
     }
}

我的问题是，有没有掉期时间复杂度更高的算法？在这种情况下O（N）。



非常感谢！





感谢您的回复。



我对交换所有元素的看法数组与每个元素的可能组合是，例如，有数组[3，-6,2,1]



我想交换每个元素以各种可能的方式，这意味着：



交换位置0中的元素，元素位于位置1（3，-6）

将元素交换到位置0，元素位于位置2（3,2）

交换位置0中的元素，元素位于位置3（3,1）

交换位置1中的元素，元素位于位置2（-6,2）

交换位置1中的元素，元素位于位置3（-6,1）

和位置2中的最后一个交换元素，其中元素位于位置3（2,1）



为此，我需要做两个循环以检查数组（就像我在程序中所做的那样）。我想问是否有更多的最佳方式来实现O（N）时间复杂度（我的是O（N2），因为两个循环为。



谢谢

My question is, is there any swap algorithm with better time complexity? In this case O(N).

Thank you very much!


Thankls for the reply.

What I ment about "swap all elements of the array with every possible combination of the elements of it" is, for example, having array [3,-6,2,1]

I want to swap every element with in every possible way, that means:

Swap element in the position 0 with element in the position 1 (3,-6)
Swap element in the position 0 with element in the position 2 (3, 2)
Swap element in the position 0 with element in the position 3 (3, 1)
Swap element in the position 1 with element in the position 2 (-6, 2)
Swap element in the position 1 with element in the position 3 (-6, 1)
And the last swap element in the position 2 with element in the position 3 (2, 1)

For that I need to do two loops in order to check the array (like I am doing in the program). What Im asking if there is any more optimal way in order to achieve a O(N) time complexity (mine is O(N2) because the two loops for.

Thanks

推荐答案

尝试使用数字1到9的输入数组运行程序，并查看结果。

我认为优化很明显如何制作O（N）。

Try running the program with the input array the numbers 1 through 9, and look at the result.
I think the optimization will be obvious how to make it O(N).

这篇关于数组的交换算法O（N）（Java）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！