antimon2_math https://blog.hatena.ne.jp/antimon2_math/ 名古屋で数学するプログラマ(仮) https://antimon2.hatenablog.jp/ CodeIQ アルゴリズム 転倒数 一昨日 の続き。通称「クロッシング問題」（実質「転倒数計算問題」）について、結城 浩 氏からフィードバックが届きました。 （解答投稿した人しか見られないらしいのでURLとか貼れませんのでご了承ください）その中で、こちらの想定していたアルゴリズム以外のものが紹介されていたので、ちょっと試してみました。 改めて、転倒数計算アルゴリズム 結城氏の紹介していたアルゴリズムは、以下の 3+1 つでした。 ナイーブな方法（＝バブルソートと同等の素朴な方法、計算量 O(n2) マージソートを使う方法（計算量 O(n log n)） 転倒表（逆転表）を使う方法（計算量 O(n log n)） （おまけ）BIT… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fantimon2.hatenablog.jp%2Fentry%2F2013%2F09%2F04%2F225924" title="もっと「クロッシング問題」（＝転倒数計算問題） - 名古屋で数学するプログラマ(仮)" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2013-09-04 22:59:24 rich https://antimon2.hatenablog.jp/entry/2013/09/04/225924 1.0 100%