A[1...n]
をn個の異なる数からなる配列にする。逆数の数を計算する
対(i, j)
は、の逆、i < j and A [i] > A [j]
と呼ばれます。
例:
A:=(2、3、8、6、1)=> Aは5つの逆数を有します。
タスク:配列A [1..nのこのようなアルゴリズムの複雑さがあると、O(N * LOGN)の逆数の数を見つける
書き込みプログラム。
A[1...n]
をn個の異なる数からなる配列にする。逆数の数を計算する
対(i, j)
は、の逆、i < j and A [i] > A [j]
と呼ばれます。
例:
A:=(2、3、8、6、1)=> Aは5つの逆数を有します。
タスク:配列A [1..nのこのようなアルゴリズムの複雑さがあると、O(N * LOGN)の逆数の数を見つける
書き込みプログラム。
この問題は、マージソートに基づいて解決できます。
厳密に言えば、手順merge(A, B)
を変更して、番号が(a, b) such that a in A, b in B and b > c
であることを返す必要があります。あなたはこの問題を解決するために必要とされる実行時間を見ることができるように
は、したがって、スタックオーバーフローにO(n * log(n))
私は試しましたが、それは真実ではありません。あなたは私のコードを助けることができます –
私はソリューションへの道を案内することができるあなたのコードを投稿してください –
ようこそマージソートの実行時間です!宿題の質問にはあなたの努力と現在のコードが表示されます。宿題の質問をそのまま放棄しても良い反応を得ることはまずありません。あなたが苦労していることを説明し、明確なデバッグ情報を提供してください。 – Aurora0001
http://stackoverflow.com/a/40001355/1040597 – Tempux