配列の逆転数を効率的に求める代表的なアルゴリズムの時間計算量は？ 2025.09.22 配列の逆転数を効率的に求める代表的なアルゴリズムの時間計算量は？ O(N) O(N log N) O(N^2) O(N log^2 N) 逆転数（ia[j] の個数）はマージソートを応用して求める方法や、座標圧縮した上でFenwick木（BIT）を使う方法が典型的です。どちらも各要素について対数時間の集計・更新を行うため全体でO(N log N)の時間で計算できます。単純比較ではO(N^2)になり大きな入力に不向きです。 クイズタグ: 競技プログラミング関連記事 競技プログラミングクイズ！【問題 全10問・答え付き】 | 2025年09月版
