問題タブ [code-complexity]

問題を解決するためにアルゴリズムを実行しましたが、その複雑さがわかりません。アルゴリズムは、グラフのすべての頂点が「良好」かどうかを検証します。「良い」頂点とは、自身が開始したパスに従って、グラフの他のすべての頂点にアクセスできる頂点です。

テストされたグラフ

私の英語に感謝し、申し訳ありません。

Landscape.ioは、PEP8、PyLint、McCabe などに基づいた優れた Python コード テストを提供します。

一部のパーサー メソッドには大きなスイッチ ブロックが含まれているため、選択したメソッドの McCabe テスト MC0001 を無効にしたいと考えています。これどうやってするの？

PyLint の次の構文を見つけました。

ソース: https://docs.landscape.io/suppressing.html

...しかし、の構文は示されていませんmccabe。私の Google の調査によると、プロジェクト内のすべてのファイルに対して McCabe ルールを無効にすることは可能ですが、これは私の目標ではありません。MC0001 をグローバルに無効にする yaml ファイルを次に示します。

ソース: https://0x7df.wordpress.com/tag/mccabe/

次の 2 つの方法は同じことを行います。時間/空間の複雑さの点でどちらがより効率的ですか?

をnA[1...n]個の異なる数からなる配列とします。

このペア(i, j)は、逆の Ifと呼ばれi < j and A [i] > A [j]ます。

例：

A := (2, 3, 8, 6, 1) => A には 5 つの逆数があります。

仕事：

アルゴリズムの複雑さが O (n * logn) になるように、配列 A [1..n] の逆数を求めるプログラムを作成します。

私はこのコードに本当に近いことをしています:

私が見つけようとしているのは複雑さです... O(n^3) を見つけましたが、この答えを「受け入れ」たくありません..基本的に 2 for(a) ループを削除すると、同じ複雑さ？

しかし、実際には、これらのコードの実行時間は同じではなく、おそらくそれほど近くないでしょう.. なぜまだ O(n^3) なのですか :/

整数の配列があるとします (例: [1 5 3 4 6])。要素は、次の規則に従って再配置されます。すべての要素は前方 (左方向) にホップし、ホップしたインデックス内の要素をスライドできます。プロセスは、2 番目のインデックス (つまり 5) の要素から開始します。要素 1 を飛び越えるか、それ自体の位置にとどまるかを選択できます。要素 1 が飛び越えることを選択した場合、要素 1 はインデックス 2 までスライドします。飛び越えることを選択したと仮定し、結果の配列は [5 1 3 4 6]。要素 3 は 1 つまたは 2 つの位置を飛び越えることができ、プロセスが繰り返されます。1 つの位置を 3 回ホップすると、配列は [5 3 1 4 6] になり、2 つの位置をホップすると [3 5 1 4 6] になります。

このようにして、要素のすべての可能な順列が可能であることを示すのは非常に簡単です。また、一意のオカレンス セットによって、最終的な構成に到達することもできます。

問題は、最終配列とソース配列が与えられた場合、ソースから最終配列に到達するために必要なホップの総数を見つけることです。AO(N^2) の実装は簡単に見つかりますが、これは O(N) または O(NlogN) で実行できると思います。また、O(N2) よりもうまくできない場合は、それを知っておくとよいでしょう。

たとえば、最終配列が [3,5,1,4,6] でソース配列が [1,5,3,4,6] の場合、答えは 3 になります。

私の O(N2) アルゴリズムは次のようなものです。移動する最後の要素であることがわかっているため、ソース配列のすべての位置を最後からループします。ここでは 6 になり、最終的な配列での位置を確認します。必要なホップ数を計算し、最終的な配列を再配置して、その要素をソース配列の元の位置に配置する必要があります。再配置ステップは配列内のすべての要素を対象とし、プロセスはすべての要素をループするため、O(N^2) になります。ハッシュマップまたはマップを使用すると検索に役立ちますが、O(N^2) になるすべてのステップの後にマップを更新する必要があります。

PSベイジアンの方法で2つの順列間の相関をモデル化しようとしていますが、これはそのサブ問題です。問題をより単純にするために生成プロセスを変更するアイデアも役に立ちます。

編集：答えが見つかりました。これは、まさにケンドール タウ距離が行うことです。O（NlogN）でこれを見つけるための簡単なマージソートベースのアルゴリズムがあります。