Java配列内のすべての要素をシフトするにはどのアルゴリズムが効率的ですか？

Question

これは私が作った最初のアルゴリズムである：

int tmp = null; 
for (int i = arr.length-1; i > 0; i--){ 
    tmp = arr[i]; 
    arr[i] = arr[i-1]; 
    arr[i-1] = tmp; 
} 

、これが私のコンピュータの先生が私に言う第2のアルゴリズムである：

int tmp = null; 
for (int i = arr.length-1; i > 0; i--){ 
    for(int j = 0; j < arr.length; j++){ 
    tmp = arr[i]; 
    arr[i] = arr[j]; 
    arr[j] = tmp; 
    } 
} 

は、より効率的であるかについての私を助けて。 100000件のデータを持つ配列で

System.currentTimeMillis(); 

この方法を使用して、私の実験では、 最初のアルゴリズムは速かったけど、私の先生は、第1の高速化、各種のものと大きなデータベースにおけるだろうと言います。私はLinkedListがうまくいくことを知っていますが、私はこの問題について知りたいのです。

Answer 1

アルゴリズムdo different things：

Input: [1, 2, 3, 4, 5] 
First: [5, 1, 2, 3, 4] 
Second: [3, 4, 1, 2, 5] 

それらが機能的に同一でないようにそれらの相対的な効率の任意の議論は、無関係です。第二はO(n^2)であるのに対し、

---

はしかし、単に何かを行うために要する時間の面で、最初のアルゴリズムは、O(n)です。そのため、入力サイズが大きくなるにつれて、最初の実行にかかる時間が2番目の時間よりも遅くなるため、先生は間違っています。

---

最初は不必要な多くの作業をやっていることに注意してください：それは、繰り返し絞っ配列の先頭に配列の最後の要素を交換しています。