アルゴリズム
アルゴリズム: 配列の長さが1以下なら、ソート済みなので終了。長さ2以上なら2へ。 配列を等分し、この2つの配列にそれぞれマージソートを適用した後、3へ。 2つの配列をマージアルゴリズムでマージする。 手順2で再帰的にマージソートを使っているので、日…
マージとは 「併合」という意味で、複数の配列や連結リストなどのデータ列を1つにまとめることをいう。 単純に複数の配列を併合するならば、それぞれの配列の長さを合計した長さ以上の配列を用意し、すべてをそこに格納してしまえばよい(順序など関係なく)…
二分木のうち、すべてのノードの値が、 [左の子の値] ≦ [自分の値] ≦ [右の子の値] となっているもの。 この図は二分探索木の条件をみたしている。 ∵ 4 ≦ 5 ≦ 8 だし、 7 ≦ 8 ≦ 9 になっている。 1. 検索 二分探索木では、データを高速に検索することができ…
各ノードの子供の数が2以下である木構造のこと。 また、各ノードが「葉であるか、次数が2(子供が2つ)」である木を全二分木(full binary tree), すべての葉が同じ深さである二分木を完全二分木(perfect binary tree) という。 図1. 二分木の例(全二分木で…
ソートアルゴリズムにおいて「安定である」ということの意味 同順序のものの順序関係が、ソート前とソート後で保たれるもののこと。 (順序が保たれないものは、「安定ではない」という) 例) 本の値段と出版年によってソートする場合を考える。 最初に出版…
DHCP (Dynamic Host Configuration Protocol) プロトコルスタック TCP/IPのアプリケーション層 下位プロトコル UDP ポート番号 67と68 (67はDHCPサーバ、68はDHCPクライアント用) 用途 TCP/IPで通信を行うためのIPアドレスやサブネットマスク、デフォルトゲ…