五十岚健夫
日语整理 官方Wiki

贪欲法

一、アルゴリズムと計算量

1. ユークリッドの互除法

欧几里得算法 (辗转相除法) -> 求两个数最大公约数的算法

源码 : 理解递归 (递归与迭代的区别)

  1. def gcd(a, b):
  2.     while b != 0:
  3.         t = a % b
  4.         a = b
  5.         b = t
  6.     return a

例题 : 用欧几里得算法求 3425 和 1233 的最大公约数
解 :

  • 3425 ÷ 1233 = 2 | 余959
  • 1233 ÷ 959 = 1 | 余274
  • 959 ÷ 274 = 3 | 余137
  • 274 ÷ 137 = 2 | 余0

2. 計算量

計算量：复杂度 再帰呼出し：递归调用 2k = n , k=log2n

データ構造とアルゴリズム - 图1

  • 線形探索：O(n)
  • 二分探索：O(log2n)

例题 : 在下列数中二分查找 34 , 并图示出来。12 , 15 , 19 , 36 , 38 , 45 , 56 , 88
解 :
12 15 19 36 38 45 56 88 ①34＜38、左へ
12 15 19 36 38 45 56 88 ②34＞19、右へ
12 15 19 36 38 45 56 88 ③34＜36、左へ
12 15 19 36 38 45 56 88 ④34 ≠ 19、存在しない

二、基本的なデータ構造

  • 配列、リスト (数组array , 链表list)
  • スタック
  • 待ち行列（キュー）、循環配列
  • 木

1. 配列

数组

挿入（そうにゅう）：O(n)
削除（さくじょ）：O(n)

2. リスト

链表

挿入、削除：O(1)
探索：O(n)

3. スタック

栈 堆栈

pop() : 出栈
push : 入栈

FILO 先入后出

4. 待ち行列

队列

enqueue() : 入队
dequeue : 出队

LILO 后入后出

循環配列：环状队列

5. 木

一つの親ノードに複数の子ノードが階層構造をもって 子を持たない末端（まったん）のノードは葉（は）と呼ばれる

構造例：

  • 子が任意数の場合

    1. class Node{
    2.   Object data;
    3.   List children;
    4. }

  • 子が二つの場合：

    1. class Node{
    2.   Object data;
    3.   Node left_child;
    4.   Node right_child;
    5. }

例题 : 列を配列で表現した場合とリストで表現した場合の違いを記述しましょう。
解 :
①配列は場所を固定するのでランダムアクセス可能であるが、挿入や削除などに時間がかかる
②リストは場所を動的に用意するので、挿入た削除が速いが、ランダムアクセスに時間がかかる

6. 木による数式の表現

葉に数値や変数を割り当て、中間ノードに演算子を割り当てる

  • 通りがけ順：親から子へ再帰的に木をのぞるときに、左→親→右
  • 行きがけ順：親→左→右
  • 帰りがけ順：左→右→親

对应 : 中序 先序 后序

(a×b) + ((c×d)÷5) 中缀
+× ab ÷×cde 前缀(前置形)
ab × cd × e÷ + 后缀(後置形)

三、集合の表現法

  • 優先度付き待ち行列、ヒープ
  • 二分探索木
  • 平衡木（へいこう）、2-3木
  • ハッシュ
  • 集合群、同値類

1. 优先队列

只能取到最小值

2. 半順序（じゅんじょ）のついた二分木