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

2165 ワード
テキストリンク
アルゴリズム(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記号(Θ)
    • を使用
    Android N Android OデフォルトMTPモードリアルタイムファイルスキャン
    [Baekjoon] 1074. Z [S1]