参考資料

Algorithms

nabetsu 2021/11/22に更新

maxの事例

アルゴリズムの効率性を測るには演算処理が何回行われるかを数えればよさそう
しかし正確な数を数えるのは現実的ではないので、key operationが実行された回数を数えるようにする
今回の事例だと <(less than operator)が何回実施されたか

最初の実装

def largest(A):
    my_max = A[0]
    for idx in range(1, len(A)):
        if my_max < A[idx]:
            my_max = A[idx]
        return my_max

この実装だとkey operation(Less than)が実行される回数はN-1回になる

Algorithmsのパフォーマンスを予測する

同じ結果を実現できる他のアルゴリズムがあったとき、どうやってどちらを使うか選択するか。

def alternate(A):
  for v in A:
    v_is_largest = True 
    for x in A:
      if v < x:
        v_is_largest = False
        break
    if v_is_largest:
      return v
  return None

このケースの場合、ベストケースとワーストケースでパフォーマンスに差がある。

ベストケースとワーストケースがあるが、ワーストケースを基準に考える？

This behavior is consistent and you can use this information to predict the runtime performance of these two algorithms on larger-sized problems

重要なのはNが増えた時に実行時間がどのぐらい増えるのか予測ができるようになること？

Time complexity as estimated by counting the number of key operations executed by an algorithm on a problem instance of size N.
Space complexity as estimated by the amount of memory required when an algorithm executes on a problem instance of size N.

Find Two Largest Values in an Arbitrary List

最大値だけでなく、大きな数2つを求める場合。

ベストケース
- less thanの実行回数は N -1 になる
ワーストケース
- less thanの実行回数は 2N -3 になる

def largest_two(A):
  my_max,second = A[:2]
  if my_max < second:
    my_max,second = second,my_max

  for idx in range(2, len(A)):
    # ここがTrueのときに一番計算回数が少なくなる
    if my_max < A[idx]:
      my_max,second = A[idx],my_max
    elif second < A[idx]:
      second = A[idx]
  return (my_max, second)

Required extra storage
Programming effort
Mutable input
Speed

Tournament Algorithms

このアルゴリズムが一番効率が良い。

N - 1のless thanが実行される。
最大値にまけた値の中で決勝に残ったものより大きな値が存在する可能性があるので、準決勝の結果も確認が必要

まとめ

nabetsu 2021/11/22に更新

Better Living Through Better Hashing

Hashingを利用することでマニュアルでサーチするより効率的に値を探すことができる

nabetsu 2021/12/05

Linked List

連結リスト（Linked List）を大学生が解説してみた　by python - アメリカの大学で奮闘中

nabetsu 2021/12/07

計算時間の測り方

同じアルゴリズムで入力の大きさの変化によってアルゴリズムの計算時間がどのぐらい変わるのかを掴むことも重要

計算時間の求め方

実際にコンピュータ上でプログラムを動かすと環境によって実行時間が変わってしまうため、計算時間の測定にはステップ数が用いられる。

実際の処理をステップ数で計測した後は、入力値の違いにより影響を受ける箇所にフォーカスしてBig O記法で表す。

Oは重要な項以外は無視するという意味が込められており、この表記によってアルゴリズムの計算時間を直感的につかむことができる。

選択ソート: $O(n^{2})$
クイックソート: $O(n log n)$

nabetsu 2021/12/10に更新

データ構造

データをメモリに蓄える際、目的に応じてうまく構造化することで利用効率を高めることができる。

だからデータ構造について学ぶ必要がある。

配列

データを一列に並べたもの。
インデックスを指定して要素にアクセスする。

データへのアクセスはしやすいが、追加や削除でコストがかかる。
(末尾なら問題ないが、途中に入れるとデータをずらす必要があるから)

スタック

データを一列に並べるが新しく追加したデータのからしかアクセスできない。(LIFO)

常に最新のデータにしかアクセスしない使い方をする場合には便利。

キュー

FIFO

ハッシュテーブル

キーとバリューのセットになっているデータを格納するデータ構造の一つ。
配列のように格納すると先頭から順に調べていく必要があり(線形探索)、時間がかかる。

そこでハッシュテーブルを使うことで、ハッシュ関数によりデータに素早いアクセスが可能になる。

ヒープ

木構造の1つ

nabetsu 2021/12/11に更新

ソート

バブルソート

右から左に向かって隣りあう２つの数字を比較して入れ替えるという操作を繰り返し行う。

Time Complexity: $O(n^{2})$

選択ソート

数列の中から最小値を検索し、左端の数値と入れ替えるという操作を繰り返す。

Time Complexity: $O(n^{2})$

挿入ソート

数字の中から最小値を検索し、左端の数字と入れ替えるという操作を繰り返す。
数列の中から最小値を探す際は線形探索を行なっている。

Time Complexity: $O(n^{2})$

挿入ソート

数列の左端から順番にソートしていく。

Time Complexity: $O(n^{2})$

ヒープソート

ヒープに数字を光順になるように格納し、ヒープから値の取り出し、ヒープの再構築を繰り返すことでソートを行う。

Time Complexity: $O(n log n})$

ただし、ヒープという複雑なデータ構造を利用するため実装も複雑になる。

マージソート

ソートしたい数列をほぼ同じ長さの2つの数列に分割していき、これ以上分割できなかったところからグループ同士をマージしていく。

クイックソート

ピボットと呼ばれる基準となる数を数列の中からランダムに一つ選び、ピボット以外の数をピボットより小さい数とピボット以上の数の2つのグループに分ける。

分割統治法の一種。

nabetsu 2021/12/11

配列の探索

線形探索

配列の前から順番にデータを調べていく。

Time Complexity: $O(n})$

2分探索

線形探索と異なりデータがソートされている場合にのみ適用できる。
配列の真ん中と目的のデータを比較することにより、目的のデータが真ん中より右にあるのか左にあるかを知ることができ、探索すべき範囲を半分に絞れる。

Time Complexity: $O(log n})$

nabetsu 2021/12/11

グラフ探索

グラフとは

幅優先探索

深さ優先探索

ベルマン-フォード法

ダイクストラ法

A*

nabetsu 2021/12/11

セキュリティのアルゴリズム

データをやり取りする際の4つの問題

盗聴
なりすまし
改ざん
事後否認

暗号の基本

ハッシュ関数

共通鍵暗号方式

公開鍵暗号方式

ハイブリッド暗号方式

ディフィ - ヘルマン鍵交換法

メッセージ認証コード

デジタル署名

デジタル証明書

nabetsu 2021/12/30に更新

Introduction to Algorithms

Binary Search

電話帳でKから始まる名前の人を探すとき、電話帳の最初から探すのは非効率。Kは真ん中辺りのアルファベットなので、電話帳の真ん中辺りから探し始めた方が効率的
あなたがFacebookでログインするとき、Facebook側であなたがアカウントを持っているか検証する必要がある。あなたのなまえがKから始まるとき、電話帳の例と同じように真ん中から探し始めたほうが効率的

これがSearch Problemという問題。

Simple Search(Stupid Search)
- 配列の前から調べていく
Binary Search
- 真ん中から調べていく

1から100の数字を当てる場合だと最大でも7 Stepで数を当てられる。
もし240000の辞書から単語を探す場合だとそれぞれのAlgorithmsで最悪のケースで以下のStepが必要になる。

Simple Search
- 240000 Steps
- $n$ Steps
Binary Search
- 18 Steps
- $log_{2}n$ Steps

Logarithms

実行時間に関して言えば、logは常に $log_{2}$ を意味する。
先ほどのSearch Problemでいうと、8個の数字をSimple Searchで探索するとき最大で8回値をチェックしないといけない。
一方、Binary Searchの場合には $2^{3} == 8$ なので、 $log8 == 3$ となり、3回値をチェックすれば良いことがわかる。

Exercies

1.1

128個のソート済みのリストがあるときに必要なステップ数。

>>> import math
>>> math.log2(128)
7.0
>>> 2 ** 7
128