TIL (2022.04.02)

2139 ワード
テキストリンク

1.グラフ


頂点(Vertex)=ノード
幹線(Edge)=頂点と頂点を結ぶ線
幹線には値があるかもしれないし、値がないかもしれない
->値=ラインウェイト
特定の頂点に関連する頂点数=回数(Degree)
隣接行列の場合)
a頂点とb頂点はつながっていますか?=O(1)
特定の頂点に関連付けられたすべての頂点=O(|V|)
隣接リストの場合)
a頂点とb頂点はつながっていますか?=O(min(degree(a),degree(b))
特定の頂点に関連付けられたすべての頂点=O(degree(a))

2. DFS & BFS


Depth First Search=深度優先ナビゲーション
深く探求して、前の過程に戻ります.
スタック実装
Breadth First Search=幅優先ナビゲーション
まずノードにアクセスし、次に隣接するノードにアクセスします.
キュー実装
最短メソッドの長さを求めるのに使用できます
理論的には性能に差はない.

3.ソート選択

  • 整数値の最小値を検索
  • その値は第1の位置
    • に置く.
    最小値の検索(
  • の最初の値を除く)
  • 、2回目の値の配置
    この手順を繰り返します.
    選択ソートの場合、時間複雑度はO(n^2)
    初回回転:1~n-1
    2回目の回転:2~n-1
    (n-1)+(n-2)+...+2+1 => n(n-1)/2 = O(n^2)
    #include <iostream>
using namespace std;

int main(){
    int n;
    cin>>n;

    int arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    for(int i=0;i<n-1;i++){
        int minVal=i;
        for(int k=i+1;k<n;k++){
            if(arr[minVal]>arr[k]){
                minVal=k;
            }
        }

        int temp=arr[i];
        arr[i]=arr[minVal];
        arr[minVal]=temp;
    }

    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}
    • 実用的な反射類ツールソース分析---SpringSideのツール類
    21.11.21 - TIL [Vue - clipboard]