🔥虚無との戦い

📝アルゴリズム

4 min read

アルゴリズムとは

Algorithms.

  • 問題を解くための計算手段.
  • 解が定まっている「計算可能」問題に対して、その解を正しく求める手続き(Wikipedia).

📝データ構造はこっち.

🔖ソートアルゴリズム

並べ替え.

📝Merge Sort

📝Quick Sort

アントニー・ホーア.

🆚昇順と降順(ascending/descending)

  • 昇順(しょうじゅん): 小さい方から大きな方へ. ascending order, asc.
  • 降順(こうじゅん): 大きい方から小さい方へ. descending order, dsec.

🔍探索アルゴリズム

🔍線形探索

linear search. 最も基本.

🔍二分探索

binary search.

🔍黄金分割探索

Golden-section search.

  • 探索範囲内で極値（最大または最小）が1つしかない単峰性関数に対して効率的に極値を求める
  • 検索範囲が約 0.618倍 に縮小され対数オーダーで収束

<2025-03-23 Sun 10:51> なにこれ、ChatGPTがいきなり教えてくれた…

📝幅優先探索

📝深さ優先探索

リスト計算系アルゴリズム

🔖累積和(cumsum)

📝スライディングウィンドウアルゴリズム

Sliding Window Algorithm. 📝リスト構造をトラバースするアルゴリズム.

リスト内の特定範囲に関数を適用して, さらにその関数適用をずらしながらリストに適用していくことを繰り返していくアルゴリズム.

Pandasだとrolling windowと呼ばれている. 窓関数とも.

時系列データの扱いのコンテクストで統計量を作成するときに現れることがおおい.

Parser Pattern

TODO: 移動先検討中…

パーサー. 構文解析器. 文字列をうけとって, 構文木を生成する関数.

📝計算量/オーダ

アルゴリズムの演算性能を表す指標.

  • Oで表記されるやつ(O記法)

2つのmaps of listをidでマージするにはMapに変換して突き合わせる

２つのjsonデータをidをキーにしてmargeするときは, 辞書に変換してからが圧倒的に効率的.

  • 辞書を使用する場合: O(n + m)
  • 直接検索する場合: O(m * n)

リストの先頭から逐次検索をするのはデータが大きくなればなるほど非効率なので前処理をしたいところだ.

競技プログラミング

わたしはAtCoderの前のTopCoder世代の人だったかな? またやりたい.

TopCoder

AtCoder

Zettels

溜まっきてたら移動.

🔗References

coursera Algorithms

アルゴリズムに対するわたしの原点.

グラフビュー

バックリンク

Recents