第1週
五つ星:https://velog.io/@monsterkos/TIL2020.08.01
コンプライアンス:https://www.notion.so/kljopuu/0fbf4ebd52d04f5d816c8d986f399283?v=6188fbb861554aa1b6b836add46f12ae

問題中心の学習

Q.
1.配列とは?
2.Pythonが提供する配列機能は?
3.並べ替えのメリットとデメリットは?
キューとは?
Enqueue,dequeueについて
5.Qの代表的な使用例は?
スタックとは?
Push、popを知っておく
7.スタックの使用例は?
8.スタックのメリットとデメリット
9.配列とチェーンテーブルの違いは?
10.linklistのノードとポインタを説明します.
11.Linked ListをPythonで実現する.
12.リンクリストの欠点は?
13.チェーンテーブルとダブルチェーンテーブルの違いは?
アルゴリズムの複雑さを計算する理由を説明してください.
時間の複雑さと空間の複雑さを説明してください.(より一般的なものを含む)
16.アルゴリズム時間の複雑さは、000によって支配される.
17.最も代表的なアルゴリズム性能標識法BigO(Big-O)を紹介する.
18.BigOでは、O(1)、O(n)、O(n二乗)の例を挙げて説明してください.
19.hash、hash table、hashing関数の違いについてそれぞれ説明する.
20.Pythonでハッシュ表からなる材料構造は?
21.ハッシュ表の長所と短所は何ですか.
22.スケジュールの複雑さは?
23.ハッシュ・テーブルの主な用途は何ですか.
24.5グリッドのハッシュテーブルを実現する
条件(ハッシュ関数:key%5、ハッシュキー作成:hash()、スロットlist)
25.ハッシュ・テーブルの最大の問題競合(競合)は何ですか.
26.衝突を解決する2つの典型的な方法を説明する.
27.バイナリツリーとバイナリ検索ツリーの違いは何ですか?
28.最安値または最安値を検索する際の時間的複雑さを用いて、Hipが何であるか、およびなぜHipを使用するかを説明する.
29.臀部とバイナリナビゲーションツリーの孔トム点の違いを説明する.
30.HIPからデータを挿入または削除する時間の複雑さはどのくらいですか?
A.
1.データをリストし、各データをインデックスに対応するデータ構造に構成します.同類データの効率的な管理に使用します.
クラスデータを順番に格納
2.リスト
3.メリット:高速アクセス(インデックス)、デメリット:データの追加/削除が難しい(最大長をあらかじめ指定しておく必要がある)
4. FIFO(first-in, first-out). 列に並ぶ.
5.「オペレーティングシステム上でマルチタスクスケジューリングを実施するためのもの」
6. LIFO(last-in, first-out). 山積みの本
7.プロセスに使用される関数の動作方法.

8.利点:1)構造が簡単で、実現しやすい;2)データ記憶／読み取り速度が速い.
欠点:1)データの最大数をあらかじめ決めておく必要があります.(Python再帰関数は1000回しか呼び出せません.1000個のスペースしか残っていないので、もっと呼び出すとエラーになります)
2)ストレージスペースが無駄になる可能性があります(ストレージスペースを最大数に拡張する必要があります).

アレイは、順次接続された空間にデータをリストする構造であり、リンクリストは、データを接続することによってデータを管理するデータ構造である.レイアウトには、事前にスペースを予約する必要があり、リンクリストが補完されているという欠点があります.

ノードは、データ値−ポインタからなるデータ記憶部であり、ポインタは、次のノードアドレスまたは前のノードアドレスを記憶する空間である.

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
    
    def add(self, data):
        if self.head == "":
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)

    def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next
    
    def delete(self, data):
        if self.head =="":
            print("해당 값 가진 노드는 없습니다.")
            return
        
        if self.head.data == data:
            temp = self.head
            self.head = self.head.next
            del temp
        else:
            node = self.head
            while node.next:
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    return
                else:
                    node = node.next
                

linkedlist1 = NodeMgmt(0)
for data in range(1,10):
    linkedlist1.add(data)
linkedlist1.desc()
print("====")
linkedlist1.delete((3))
linkedlist1.desc()

1)アドレス情報用の独立したデータ空間が必要であるため,リストより記憶空間の効率が低い.
2)接続情報の検索に時間がかかるためアクセス速度が遅い.
3)中間データを削除する場合,前後データの接続を再構築する必要があり,効率が低下する.

デュアルチェーンテーブルは、「前のノードアドレス」-「データ」-「次のノードアドレス」から構成されます.linked listの欠点は、前からデータを検索しなければならないことです.ノードが1000個あり、検索するデータが最後にある場合は、1000回検索する必要があります.このような欠点を補うために現れたのはdoublelinklistで、後で検索することもできます.

どのアルゴリズムが良いかを分析するために.(一つの問題を解決する方法はいくつかあります)

時間複雑度はアルゴリズム実行速度である.スペースの複雑さは、アルゴリズムで使用されるメモリサイズです.

複文.変数個数,ifゲート個数などの時間複雑度への影響は相対的に小さい.

O(N)で表記された最大/一般的に用いられる.
アルゴリズムの最悪の実行時間を表す(=最悪でもこのような性能を保証できることを意味する)
-ちなみに、時間の複雑さは最大の計算のみで、定数は無視されます.
−2 nの場合,時間複雑度はO(n)であった.
−n＋10の場合,時間的複雑度はO(n)であった.
−n二乗＋n＋3の場合,時間複雑度はO(n二乗)であった.

1からnの値を出力する関数を作成します.
1)繰り返し文を作成し,n回ループすると,時間複雑度はO(n)となる.

def sum_all(n):
    total = 0
    for num in range(1, n + 1):
        total += num
    return total

2)繰り返しなしで以下のように記述すると,nの値にかかわらずコードは1行実行されるので,時間的複雑度はO(1)である.

def sum_all(n):
    return int(n * (n + 1) / 2)

3)(上記の問題とは異なる)所与のnを2ゲートとし,時間複雑度はO(n二乗)であった.

1)ハッシュ(hash)とは、任意の値を固定長に変換することを意味する.
2)ハッシュテーブルはkeyにvalue(データ)を格納する資料構造である.
3)ハッシュ関数(hashing function)は、「任意の長さのデータを入力して指定された長さの結果を返す関数.

専制的

メリット:
1)データの保存と検索速度が速い.
2)ハッシュキーに一致するデータ(重複)があるかどうかを容易にチェックする.
欠点:
1)一般的には、より多くのストレージスペースが必要です.
2)複数の鍵に対応するアドレスが同じである場合,競合を解決する方法が必要である.(競合解決アルゴリズム)

一般的に(衝突なし)はO(1)
最悪の場合O(n)

大量の検索が必要な場合は、

が必要です.

頻繁に保存、削除、読み取り

キャッシュ(再検証が容易)

1)まず5マス目のチェックを作ります.
2)入力したキー値を0～4のいずれかに変換します.(5グリッドなのでインデックスは0~4).
具体的には,a)キーを先にデジタル化し,b)5を除いて余剰を求める方式をとる.
3)求めたインデックスに値を入力します.
4)データを読み取る場合は,鍵を入力するだけでデータを抽出する.

hash_table = [i for i in range(5)]

def get_key(key):
	return hash(key)

def hash_func(key):
	return key % 5

def store_data(key, value):
	key = get_key(key)
    hash_address = hash_func(key)
    hash_table[hash_address] = value

def read_data(key):
	key = get_key(key)
    hash_address = hash_func(key)
    return hash_table[hash_address]    

衝突はハッシュ関数によって同じhash addressを得たときに発生する問題である.
(1軒のみ、2人は同じ家の住所に割り当てられています)

Chaining技術とLinear Probing技術があります
Chainingテクノロジーはlink listに割り当てられた同じアドレスのデータを後で接続することで問題を解決する.
ハッシュ・テーブルを使用して空間外の空間を格納する方法.
Linear Probingテクノロジーは、ハッシュ・テーブル・ストレージ領域で問題を解決する方法です.
競合が発生した場合、hash addressの次のaddressから順にナビゲートし、最初に発生した空白領域にデータを格納します.

バイナリツリーは、ノードの最大枝分かれ数が2のツリーです.バイナリ・ナビゲーション・ツリーはバイナリ・ツリーですが、左ノードの値がノードより小さく、右ノードの値がノードの値より大きいという追加のルールがあります.

データの最大値と最小値をすばやく検索するための完全なバイナリツリー
->完全に李金特里?ノードを挿入するときに左側のノードから順に挿入するツリー.

なぜお尻を使うのですか?

配列にデータを入れて最大値と最小値を検索するにはO(n)が必要であり、hipではO(logn)が必要である.
-優先キューなどの最大値または最小値をすばやく検索する必要があるデータ構造およびアルゴリズムを実装します.

共通点:両方ともバイナリツリーです.
差異:

hipは、各ノードの値がサブノードより大きいか等しいかを示す(最大heapの場合)

バイナリ・ナビゲーション・ツリーの左側のサブノードの値は最小で、右側のノードの値は最大です.

結論:バイナリナビゲーションツリーはナビゲーションに使用され、hipは最大/最小値を検索するために使用されます.

n個のノードを持つheapでデータを挿入または削除する場合、最悪の場合、ルートノードをリーフノードに比較する必要があります.𝑙𝑜𝑔2𝑛 時間の複雑さが近い𝑂(𝑙𝑜𝑔𝑛)