アルゴリズムとデータ構造 学習体験

I. データ構造とは？アルゴリズムとは？

 データ構造とは、コンピュータがデータを格納し、整理する方法であり、アルゴリズムとは、データを操作するための一連の方法である。

II.何のために？

 1) 時間の複雑さを書く& 空間複雑度の低い優れたコードである。
 2) 問題の考え方

III.どのように使われるのですか？

1) 時間の複雑さ
2)空間の複雑さ
3)平均時間複雑性
4)等しくなる。

IV.よく使われるものは何ですか？

 1)  - ArrayList 
 2)  - LinkedList 

V. 一般的なデータ構造とアルゴリズムの使い方

単一のリンクされたテーブルを反転させる3つの方法：スタックを使用する方法とその場での反転

では、実際にどちらを選ぶべきなのでしょうか？

スタックの特性を利用して反転を実現

付加的な空間の複雑さは、チェーンテーブルの長さO(n)によって決定され、時間の複雑さは、アクセスが線形時間O(n)

所定の位置にリバース

余分な空間の複雑さ newHeadをO(1)として導入、時間の複雑さはO(n) リンクテーブルの長さで解決。

static Node reverseByRecursion(Node head){
 if(head == null || head.next == null){
 return head;
 }
 Node newHead = reverseByRecursion(head.next);
 head.next.next = head;
 head.next = null;
 return newHead;
}

その場での反転

空間の複雑さはpreNodeとnextNodeのために追加されるのでO(1); 時間の複雑さはチェーンテーブルの長さO(n)

class Node {
 int data;
 Node next;
 Node(int data){
 this.data = data;
 }
}
Node reverseByLoop(Node head) {
 if (head == null || head.next == null){
 return head;
 }
 Node preNode = null;
 Node nextNode = null;
 while (head != null){
 nextNode = head.next;
 head.next = preNode;
 preNode = head;
 head = nextNode;
 }
 return preNode;
}

 実装スキームの一般的な選択では、空間の複雑さから& 上記から、その場反転スキームが優先されるべきであることがわかる。& 時間の複雑さは同じで、解決策をどう選ぶか？