すべての人に向けたコンピュータ科学研究−第4回

アルゴリズム(Algorithms)
1.検索アルゴリズム

メモリをバイトメッシュと見なし、データ構造

を使用することができる.

コンピュータの感知能力X

コンピュータは、アレイ内のコンテンツを1つずつチェックする必要がある

.
せんけいたんさく

配列の最初の要素からインデックスを1つずつ移動し、値が存在するかどうかを確認します.

のソートされていないアレイの場合、線形検索の効率が向上します.
バイナリサーチ

分割征服技術を使用して、アレイの中央要素から、現在の要素が検索する値より大きい場合は左側に、値が小さい場合は右側に繰り返し、

を確認する.
2.アルゴリズム表記法

アルゴリズムは、線形、少し曲がった、またはログ形状のアルゴリズムであり、

である.

コンピュータ科学者は特定の用語を使用してアルゴリズムを記述する:アルゴリズムの設計がどれだけよくて、コードの実現がどれだけ良いか

で最も一般的なBig-Oシンボル(アルゴリズムの実行に要する時間上限)は

である.

Big−Oの近似推定値は、入力値が大きくなると同じ直線上に収束するので=>を表す.

実行時間:プログラムまたはアルゴリズムの実行に要する時間(数回の計算)

O(n^2)
O(nlogn)
O(n)    // 선형 검색 
O(logn) // 이진 검색 
O(1)

Ω:アルゴリズム実行に要する時間下限

Ω(n^2)
Ω(nlogn)
Ω(n)    // 배열의 길이/개수 계산 
Ω(logn)
Ω(1)    // 선형 검색, 이진 검색

3.線形検索

配列に入れる値が予め分かっている場合は、カッコ({})を使用して1行

として表すことができる.

int numbers[3] = { 1, 2, 3} 

関係演算子(==)は文字列には使用できません.2つの文字列を比較するには、

を使用して、文字列内で文字=>strcmpを1つずつ比較する必要があります.

の欠点は、関連情報を個別に配列として定義すると、「常に同じインデックスに存在する」ことが保証されにくいことです.

構造体(struct)はCで予め定義されたキーワードであり、1つのボウルのように複数の資料型を収容することができ、一度に関連情報を組み合わせて表現することができる.
4.泡の位置合わせ

互いに比較し、

で再配置する

の外反複文n-1回を繰り返し、比較基準点が内反復文n-1回であるか、比較対象

より大きいか小さいかを計算する.

O(n^2)

Ω(n^2)

5.ソート選択

組、前後順に交換しないで、毎回1つの目標があって、最小の値を探して、それから小さい値で、

O(n^2)

Ω(n^2)

6.ソートアルゴリズムの実行時間

Bubbleソート:条件式を追加(交換なしで繰り返す場合のみ)実行時間をO(n)

に短縮
7.再回帰

既存の問題よりも小さい問題を解く

8.連結ソート

から入力が1つしかない場合は、

がソートされているとみなされる.

まず左揃え、右揃え、次にトリミング、すなわち1つの配列にマージ、マージ後の配列も

である.

O(nlogn)

Ω(nlogn)

上限と下限を同時にTheta記号(Θ)

を使用