アルゴリズム第1週TIL

📌 Chapter 1-アルゴリズム効率分析

📚 アルゴリズムの由来

アルクォリズミ:名前がラテン語に変換されるにつれて、アルゴリズムという用語が使われます.

最初のアルゴリズムはユークリッドの最大公約数アルゴリズムである.
:2つの自然数の最大公約数は、小数と小数を差し引いた最大公約数に等しい!
ex) (18,6) == (12,6) == (6,6) == (0,6)
2つの数のうちの1つが0の場合、残りの値は最大公約数です!

📚 アルゴリズムとは?

問題のシステムソリューション

は常に有効なアルゴリズムを制定することが非常に重要である

A set of unambiguous instructions for solving a problem or subproblem in a finite amount of time using a finite amount of data

📚 アルゴリズムとくせい

精度/実行性/有限性/効率(時間、空間複雑度)

📝 最低価格の検索

シーケンシャルナビゲーション:最大の数字を変数に入れて逐次比較する方法

📝 任意の数値を検索

シーケンスナビゲーション
: n

二分探索(Binary Search)
: log n +1
:ソートであれば二分探索の方が効率的ですが、ソートがなければシーケンス探索の方が効率的です.すなわち,資料の構成によって効率が異なる.

📚 アルゴリズム実行時間

アルゴリズムの実行時間を決定する基準は多様であってもよい.
(ループの繰返し回数、関数の呼び出し回数等)

ex)forサイクルn^2 x最大値を求める場合、少なくともn/2=n^3

sample(A[],n){
sum=0;
for i = 1 to n
	for j = 1 to n{
    	k= A[1 ~ n] 에서 임의로 n/2 개 뽑았을 때 최대값;
        sum=sum+k;
   	}
    return sum;
}

📝 フィボナッチ

再帰方法

int fib(int n){
	if(n<=1)
    	return n;
    else
    	return (fib(n-1)+fib(n-2));
}

fib(n)を計算する関数呼び出し回数

T(n):fib関数を呼び出してfib(n)を計算する回数
T(0) = 1
T(1) = 1
T(n)=T(n-1)+T(n-2)+1(初めての運転なので)

 > T(n-2) + T(n-2) == 2xT(n-2)
 📌 T(n-1) > T(n-2) 이므로!!
 📌 T(n-2) = T(n-3) + T(n-4) +1 > 2 x T(n-4)
 > 2^2 X T(n-4)
 > 2^3 X T(n-6)
 .
 .
 .
 > 2^n/2 X T(n-n) = 2^n/2 X T(0) = 2^n/2

: T(n) > 2^n/2
:フィボナッチ再帰アルゴリズムの実行速度が遅い.どうしたんですか.計算を繰り返しすぎた.

繰返し方法

int fib2(int n){
	index i;
    int f[0~n];
    f[0]=0;
    if(n>0){
    	f[1]=1;
        for (i=2; i<=n; i++){
        	f[i]=f[i-1]+f[i-2];
        }
        return f[n];
}

: T(n) = n+1
:計算を繰り返していないので、だいぶ速くなりました