問題タブ [inversion]

MergeSort を使用して MATLAB で反転カウンターを実装しようとしていますが、何らかの理由で、いくつかの答えが間違っています。たとえば、[3, 4, 8, 1] の反転数は 3 ですが、2 になっています。ただし、配列は正しくソートされているので、分割反転のカウント方法はが問題です。

これが私のコードです：

C++ で LAPACK を使用して、複雑な行列を反転しています。具体的には、私が使用している2つの機能は次のとおりです。

zgetrfLU分解用。

zgetri反転のために。

コードを最適化するという私の目標として、タイミングについて質問があります。LAPACK で一般的な行列反転法を使用する場合 (使用する関数がより適切で迅速な場合はお知らせください)、関数のタイミングは行列の値とは無関係ですか?

たとえば、人口密度の高い行列を反転するよりも単位行列を反転する方が速いでしょうか?

繰り返しますが、複素行列の一般的な LAPACK 反転に関してこの質問をしていることを強調したいと思います。私は、使用できるさまざまな三重対角関数とバンド関数について知っています。

行列のすべての要素が複雑な double であると想定しています。

ありがとう、ケビン

基本的に、順序が乱れている配列内のペアの数を決定するアルゴリズムを Java で記述しようとしています。したがって、i と j を取り、j が配列内で i よりも高い位置にあるが、A[i] > A[j] の場合、これら 2 つの数値は反転としてカウントされます。現在、これは私が持っているものです：

これが行うことは、互いに隣り合っているペアのみを比較するため、これを変更して、配列内で下の位置が上の数値よりも高い値である 2 つの数値を見つけようとしています。私はそのようなことをする方法を知っていますが、実行時間を (n+k) にしたいです。ここで、n は配列の長さ、k は配列内の反転の数です。

編集:挿入ソートを実装する私の試みは次のとおりです。

k は、反転の数を追跡することになっています。配列 5、4、3、2、1 の場合、返される数値は 6 です。そうですか?

配列内の反転の数を数えようとしています。4 になるはずの結果が 3 になっています。これが私のコードです。

なぜこれを行うのか誰にも分かりますか？ありがとう

マージソートで配列をソートしながら反転をカウントしたい。その目的のために、条件に変数を追加して、反転が発生するたびにこれがインクリメントされるようにしました。擬似コード:

ただし、複雑さが同じままかどうかはわかりません: O(n log n)。

変数を 1 つだけインクリメントすると、WC の複雑さが悪化しますか? 私が知っているように、それは最大の被加数 (n-factor) のみに依存します。また、定数を追加するか、最悪の場合 (n - 1) + (n - 2) = 2n - 3 のインクリメントを追加すると、複雑さが大きく変わりますか? はいの場合、何を提案しますか?