アルゴリズム第1週TIL

1977 ワード
テキストリンク

📌 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
    :計算を繰り返していないので、だいぶ速くなりました
    jQuery機能関数の詳細
    [プログラマー]正常な矩形/python/薬水と倍数