カテゴリー: データ構造

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

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

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

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

形式的冪級数を \(\sum a_n\frac{x^n}{n!}\) の形で取ると意味のある畳込みが計算できてなぜか上手くいくことがある。この指数型母関数と呼ばれる形で上手くいくのはどんな場合か、またその性質を積極的に利用して考察に生かせないのか。解説しよう。

\(r\) 頂点完全グラフ \(K^r\) を含まない辺の数が最大のグラフとは何か。この疑問に答える Turán の定理を解説しよう。

素数が絡む計算量解析を解説。

アルゴリズム/データ構造のLTの発表リストや資料のまとめ。

Union Find の計算量を解析します。