アルゴリズム定義

:問題を解決できる定義が良好な有限時間内に終了する計算プログラム.
AlgorithmとMethodの違い
アルゴリズムは限られた時間で終わりますが、methodは限られた時間で終わることを知りません!

アルゴリズム解析方法

問題のマーク方法

題:答えを探す質問

パラメータ(パラメータ):問題で値が指定されていない変数

入力

:パラメータの特定値

を指定します.

出力:入力された質問の答え

Ex 1.1) Sorting

題:n個の数字のリストSを非降順に並べ替える(並べ替える)

パラメータ:S,n

例(例)–パラメータの値が

の場合
Ex 1.2) Searching

題:どの数xがn個の数のリストSにあるかを決定する.Sでは、ない場合は「いいえ」

と答えてください.

パラメータ:S,n,x

ぎじふごう

:直接実行できるプログラミング言語ではありませんが、計算プロセスを表現するための実際のプログラムにほぼ近い言語です.簡潔かつ正確に意味を表す.アルゴリズムは擬似コードを用いて表現される.
アレイ
:共通の性質を持つ複数の変数の場合、変数名を定義します.
変数を表すインデックスを使用したデータ構造(datastructure)
[アレイに格納されている最大10個を検索]

Pseudo-code
1)a[0]のデータを一時的に最大値Mに設定
2)a[1]の値をMと比較し、a[1]が大きい場合はa[1]をMにリセットするか、a[2]を比較a[2]の値に移動する
3)残りのデータに対してステップ2を実行する
4)Mはデータの最大値である

フローチャート

Examples

Alg 1.1シーケンス探索アルゴリズム

Pseudo-code

インプリメンテーション
1) Python

# Seqeuntial Search

def seqsearch(s, x):
    loc = -1
    for i in range(len(s)):
        if s[i] == x:
            loc = i
    return loc

s = [3,5,2,1,7,9]
loc = seqsearch(s,4)
print(loc)

Alg 1.2配列の数を追加

Pseudo-code

インプリメンテーション
1) Python

# Sum of elements of array

def sum1(s):
    result = 0
    for a in s:
        result += a
    return result

def sum2(s):
    result = 0
    for i in range(len(s)):
        result += s[i]
    return result

s = [3,5,2,1,7,9]
answer1 = sum1(s)
answer2 = sum2(s)

print(answer1, answer2)

Alg 1.3交換ソート

Pseudo-code

インプリメンテーション
1) Python

# Select1ion Sort - nondecreasing order
def Selection_Sort(S):
    for i in range(len(S)):
        for j in range(i+1, len(S)):
            if S[j] < S[i]:
                temp = S[i]
                S[i] = S[j]
                S[j] = temp
    return S

s=[3,2,5,7,1,9,4,6,8]
s = Selection_Sort(s)
print(s)

Alg 1.4行列の積

Pseudo-code

インプリメンテーション

# Matrix Multiplication

def Matrix_Multiplication(a, b):
    result = [[0] * len(b) for row in range(len(a))]
    for i in range(len(a)):
        for j in range(len(b)):
            for k in range(len(a[0])):
                result[i][j] += a[i][k] * b[k][j]
    return result

a = [[1,2], [3,4]]
b = [[4,1], [1,0]]
print(Matrix_Multiplication(a,b))

Alg 1.5 Binary Search

Pseudo-code

インプリメンテーション

# Binary Search
def binary_search(data, item, low, high):
    location = -1
    while (low <= high) and (location==-1):
        mid = int((low + high) / 2)
        if data[mid] == item:
            location = mid
        elif data[mid] > item:
            high = mid-1
        else:
            low = mid+1
    return location

data = [1,3,5,6,7,9,10,14,17,19]
n = len(data)
location = binary_search(data, 9, 0, n-1)
print(location)

Alg 1.6 Fibonacci

Pseudo-code
1)復帰(復帰)

2)反復(反復)

インプリメンテーション

# Fibonacci

# Recursive way
def fib1(n):
    if n <= 1:
        return n
    else:
        return fib1(n-1) + fib1(n-2)

# Iterative way
def fib2(n):
    fib = [0 for i in range(n+1)]
    if n > 0:
        fib[1] = 1
        for i in range(2,n+1):
            fib[i] = fib[i-1] + fib[i-2]
    return fib[n]

アルゴリズムの分析

分析メソッドのタイプ

Every-case analysis

:Input dataに属するsizeのみから.Inputデータの値には関係ありません.

Worst-case analysis

Average-case analysis

Best-case analysis