JavaでLinkedListを反転するこのアルゴリズムがθ（N）に合わないのはなぜですか？

Question

私が持っている課題についての質問は、新しいリストを生成するLinkedListをθ（N）回反転するアルゴリズムを書くことです。

私が思いついたコードは、時間の要件を満たしていないため、私はその理由を理解できません。

public Node reverse() { 

    if (this == Node.NIL) { 
     return Node.NIL; 
    } 

    if (this.getNext() == Node.NIL) { 
     return new Node(this.getItem(), this.getNext()); 
    } 

    Node curNode = new Node(this.getItem(), this.getNext()); 
    Node front = curNode; 

    Node nextNode = null; 
    Node prevNode = null; 

    while (curNode.getNext() != Node.NIL) { 
     nextNode = new Node(curNode.next.item, curNode.next.next); 
     curNode.next = prevNode; 
     prevNode = curNode; 
     curNode = nextNode; 
    } 

    curNode.next = prevNode; 
    front.setNext(Node.NIL); 
    return curNode; 
} 

あり、常に逆転させるために用意リストに作成された最初のノードであるNode.NILと呼ばれるべきNILと呼ばれるノードがあるので、Node.NILは次のノードである場合は、になりますリストの最後。

各ノードには、「next」と「item」の2つの属性があります。「next」はリストの次のノードで、「item」は持ち歩くデータで、この場合はObjectです。

これは（NCASES = 20）が使用されている試験である：

@Test 
public void testReverseTiming() { 
    int i; 
    long diff = 0; 
    for (i = 0; i < NCASES - 1; i++) { 
     long start = System.nanoTime(); 
     Node result = nodes2[i].reverse(); 
     long end = System.nanoTime(); 
     diff = end - start; 
     if (diff/1000000 > 250) { 
      i++; 
      break; 
     } 
    } 
    long start = System.nanoTime(); 
    Node result = nodes2[i].reverse(); 
    long end = System.nanoTime(); 
    long diff2 = end - start; 
    double ratio = (double) diff2/(double) diff; 
    assertTrue("reverse should scale linearly with list size", ratio > 1.2); 
    assertTrue("reverse should scale linearly with list size", ratio < 2.5); 
} 

それは1.2と2.5の間であることが必要であるのに対し、自分のコードは、25から35までの範囲を生成する比率。

Answer 1

あなたのコードは1回だけリストを反復しているようですから、実際はO（n）と思われます。

ただし、実際のパフォーマンスはメモリ割り当て（大規模なデータセットのOSコールを含む）とガベージコレクションに依存するため、外観内にオブジェクトを割り当てます（new Node()）。どちらも不確定な時間がかかります。これは、アルゴリズム（理論上は）がO（n）であっても、測定ランタイムがn以外の要因に依存することを意味します。

新しいノードを作成する代わりに、既存のノードのリンクを変更するアルゴリズムを書き直そうとする必要があります。 （私は割り当てが既存のリストを元の位置に戻し、リストの逆コピーを作成しないと仮定します）