資料構造とアルゴリズムに関する理論学習を整理する.

データ構造

資料構造の定義:コンピュータ科学全体の観点の基礎工学概念
(どういう意味ですか…)コンピュータの機能を効率的に動作させるための何らかの構造と見なすことができる.
たとえば、ビジネスの自動化、高速計算(計算機)、繰返し処理、複数の値のバッチを効率的に処理できる構造を構築します.

データ構造と効率

データ構造を利用するのは効率を高めるためです.実際に利用するサービスが少し遅れたり遅くなったりすると不便になるように、速度面での効率が重要であり、メモリの使用効率が高くないのも望ましくありません.これらの点を把握しているのは時間の複雑さと空間の複雑さです.

時間複雑度:実行時間を決定します.S/Wの性能と見なすことができる.

スペースの複雑さ:問題を解決するために必要なメモリストレージスペースを決定します.H/W性能.

Big(O)記号

これは、N個のデータに対して何回演算を繰り返したり操作したりするかによって、時間的複雑度の表現方法である.すべてのイベントに対して正確な時間を決定することはできません.したがって、重複する方法と有無に応じて、階層的に確認します.
O(1)O(1)O(1)-一定時間:一次単純演算を表す
O(logn)O(logn)O(logn)O(logn)-ログ時間:いくつかの要因により、繰り返し計算の回数が減少
O(n)O(n)O(n)−線形時間:データN全体を一次線形演算する
O(nlogn)O(nlogn)O(nlogn)-線形ログ時間:すべてのデータ演算を実行する必要がある場合があります.演算数はn87 log 2 n*log 2 n87 log 2 nである.
O(n 2)O(n^2)O(n 2)−二乗時間:データN全体を二乗演算する.
O(Cn)O(C^n)O(Cn)−指数時間:故障排除のための演算が指数関数的に増加する.定数のn次方程式を計算する必要がある.
これにより時間的複雑度(Time Complexity)を区別することができ,各アルゴリズムの性能を大まかに評価する際にこれに基づいている.
上の大きな(O)タグは,時間が少なければ少ないほど性能が良くなり,不要な演算量を最小限に抑えて性能を最高にすることを目標としているといえる.

ADTデータ構造-抽象

基本文字列(STRING)整数や実数(INT、FLOAT)などのデータ型をスキップし、ADT関連のデータ構造を知る.
抽象データ型と呼ばれるデータ構造がある.
これは資料構造であり、抽象的で概念的な理論でその構造を理解してこそ、このようなアーキテクチャを作成し、使用することができる.

1.STACKスタック-最初のアウトバウンド（LIFO）

スタックとは,後入先出,最後入先出の資料構造を指す.
何かを積み上げた後、取り出すときに一番上のものを取り出すのが原理です.
日常生活でも多く見られますが、例えば宅配箱をトラックに積むときは、一番遅く降りたものを先に積んで、すぐに降りた最後のものを詰めます.

特長

は、1つの場所でしかデータを入れたり取り出したりできません.

データの入力はPush、出力はPopです.

-キャンセル/後退ページ等

を利用する.

スタックオーバーフロー:

上記のスタックで割り当てられるメモリを超える現象を指し、再帰関数が無限に持続したり、1つの関数で過大な領域変数を宣言したりすると、このような状況が発生します.開発者の情報共有で有名なプラットフォームの名前もそうです.

コスト:

勉強した上は、似たような名前も一緒に知っているだろう.これは、物事を処理する間接的な時間を意味し、なくてはいけないが、最小化すればいい子だ.
例えば、水を飲むためにコップを洗って水を受けて飲む必要がある場合は、問題を解決する方法は水だけを飲むことですが、そのために私たちが取った行動(コップを洗う)の時間はオーバーヘッドです.
コップを10秒洗い、水を3秒受け取り、約2秒飲んだ.では全部で15秒使いましたが、水を飲む2秒以外は13秒が出費です.この費用を減らす方法はありますか?コップをきれいに洗うことです.もしそうなら、10秒で必ず水を受け取る3秒のオーバーヘッドを減らすほか、大幅に減らすことができます.

2-1. QUEUEキュー-最初の入力(FIFO)

先入先出の資料構造.基本的なキューを考えればいいです.通常、ホテルに並んでいる場合も、先に並んでいる人が先に入場するのと同じ原理です.
いくつかの対戦ゲームでは、準備ができてからゲームを開始しようとすると「Qを回す」と表現され、このときの「Q」は資料構造のQueueである.名前の通り、行列を考えればいい.

入出力位置が異なります.

FrontとRearは、それぞれ入力をEnqueue、出力をDequeueと呼ぶ.

データへのアクセスは、Frontの先頭またはRearの末尾のデータのみでアクセスできます.

利用率-コールセンター電話接続、プリンタ(印刷入力優先)

2-2 DEQUEインデックス-双方向キュー

コレクションパッケージにdequeというモジュールが存在するインデックスは、キューとスタックを統合するか、双方向キューと言える.キューの構造によって、前後とも入力と出力が可能になるからです.
入力または出力の順序はスタックやキューではないため,必要な部分で先に出力できるため,時間的複雑度はO(1)であり,非常に効率的な資料構造である.

3.リンクリスト-接続リスト

動的配列構造を有するデータ構造の接続リストは、各リストを接続する概念と見なすことができる.ノードはデータ価値領域とアドレス領域に分かれているため,前後リストを接続して配列する.

上の接続リストの画像を表示すると、ノードは左側に値があり、右側にアドレス値があります.
上記ノードのアドレス値は、次のノードのアドレス値「接続」として配列されており、これが接続リスト構造である.

各ノードはメモリに上の画像のようにそれぞれ格納され、各ノードは後ノードに接続されたように格納、挿入、削除される.

PythonのListリポジトリでは、各ノードがindexで値を検索でき、メモリの割り当ても上の画像のようにデータを貼り付けて格納します.
接続リスト

の最初のノードをheadと呼び、最後のノードをtailと呼ぶ.

は、ストレージ領域においても、挿入、削除においても、Pythonリスト資料型よりも有効である.
挿入する場合は、2つのノード間にノードを挿入し、ポインタ(アドレス)接続を修復するだけで、削除プロセスも簡単です.したがって,挿入・削除に関わる時間的複雑度はO(1)であり,単純な演算で行う.

の探索ではPythonのリストよりも効率が低い.
PythonリストはIndexで一度に値の位置を見つけることができますが、接続リストについてはheadからナビゲートする必要があるため、最悪の場合はn回チェックする必要がある場合があります.O(n)複雑度.

class Node:
  def __init__(self, value, next=None):
    self.value= value # 노드의 값을 나타내는 value
    self.next= next # 노드의 다음위치를 가리키는 next. 초기값이 None
class linked_list:
  def __init__(self, value):
    self.head = Node(value) # 초기 클래스에 head 선언. 첫번째(헤드의) 값이 주어진다.
  def add_node(value):  # 노드를 추가하는 함수
    node = head         # 첫번째 위치에 해당하는 head를 생성한 뒤, node변수에 저장해둔다.
    while node.next:    # node.next가 None아닐떄 (add_node를 두번 이상 했을때를 의미) 반복문 진행
      node = node.next  # node 변수에 다음 노드를 넣어준다. 
      print('print in while:', node.next)
    node.next = Node(value) # 데이터를 노드 다음 위치로 저장
    
link = linked_list(30) # 먼저 헤드에 30을 입력해본다.
link.add_node(13) # 이후 노드를 추가하면 뒷쪽에 붙는다. (삽입이 아니다)
link.add_node(15) # 하나 더 붙인뒤 확인해본다.

print(link.head.value)			# 헤드값 출력
print(link.head.next.value)		# 헤드 다음값 출력
print(link.head.next.next.value)	# 고 다음값 출력

[output]
30
13
15

この接続リスト構造のコード実装について簡単に説明した.挿入と削除は削除してnextを接続するだけです.次は正式な探索に関する資料構造とアルゴリズムである.