カテゴリー: データ構造

グラフ理論の用語の定義は人によって揺れがあります。…

2-factor theorem と言われる定理を証明します。

Reinhard Diestelのグラフ理論を読み…

永続セグメント木・永続遅延セグメント木のアルゴリズムを解説する。

原始根についてアルゴリズムの観点から解説する。

この記事では部分永続配列（fat nodes）と全永続配列（永続 m 分木を流用）を解説する。永続配列を使うと、いくつものデータ構造が機械的に永続化できる。

理論的に最良な最悪計算量 \(O(\log(n)/\log(\log(n)))\) を実現する Union Find を紹介する。

全永続 Queue の一種である銀行家の Queue（Banker’s queue）を解説する。

最大独立集合問題を解くアルゴリズムを解説する。この問題は NP困難であることが知られており、多項式の計算量で解くことはできない。しかし、指数の底を改善することで速度を大幅に向上することができる。

この記事では辺空間の部分空間であるサイクル空間、カット空間の基底について解説する。