第一章緒論

は、ループ関数を使用するよりも、再帰関数がより多くの空間を占有し(問題解決方法の効率は空間の利用効率に関係する)、再帰呼び出しのすべての関数を同時に記憶し、呼び出しが終了するまで記憶空間を解放する必要がある.

多項式を計算する場合、結合則f(x)=a_0+x(a_1+x(…(a_(n-1)+x(a_n))(秦九韶アルゴリズム)は、階乗アルゴリズムよりも所要時間が少なく、乗除法よりも加算減算法の方がずっと速い.

抽象データ型:オブジェクト向け言語の定義がより良い

タイプ名:Matrix

データオブジェクトセット:マトリックスの要素と行列

操作セット:行列乗算、加算等

複雑度T(n)を解析する場合、「最悪複雑度」と「平均複雑度」があり、最悪複雑度がよく用いられる.

大Oは法で表される複雑度の上界を表し、Ω(n)は複雑度の下界を表し、θ(n)は上下の境界が等しいことを表す.

複雑度ソート:1

の2つのアルゴリズムが結合されている場合、複雑度が加算されます.2つのアルゴリズムがネストされている場合、複雑さが乗算されます.

forサイクル複雑度はサイクル回数にサイクルボリュームコード複雑度を乗じ,if−else構造複雑度はif条件判断と2つの分岐のうち,複雑度が最も大きいものである.

「分而治之」思想、オンライン処理思想:1つの数字を入力するたびに処理され、いつでも終了しても現在の入力の解を得ることができる.

にぶんたんさくかんすう

#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /*                 */
};

List ReadInput(); /*     ，    。     1     */
Position BinarySearch( List L, ElementType X );

int main(){
    List L;
    ElementType X;
    Position P;

    L = ReadInput();
    scanf("%d", &X);
    P = BinarySearch( L, X );
    printf("%d
", P);

    return 0;
}

Position BinarySearch(List L, ElementType X){
	Position lower,mid,upper,position;
	lower = 0;
	upper = L->Last;
	while(lower<=upper){
		mid = (lower + upper) / 2;
		if (L -> Data[mid] > X)
			upper = mid - 1;
		else if ( L -> Data[mid] < X)
			lower = mid + 1;
		else 
			return mid;
	}
	return position;
}