問題タブ [code-complexity]

挿入ソート用に以下のコードを作成しました。従来のアプローチの代わりに、関数呼び出しを使用してコードを記述することにしました。しかし、コードの複雑さを見つけることができません。時間と空間の複雑さと、従来のアプローチとの違いを見つけるのを手伝ってください。

以下は、挿入ソートの従来のアプローチです。

抽象化とカプセル化について議論している他の投稿を読んだことがありますが、それらを理解しているとは確信が持てません。または、理解はしているが、内容の明確さに不満を感じているかもしれません。抽象化とカプセル化に関する私の理解は次のとおりです。それらはどのような点で正確/不正確/完全/不完全ですか?

「抽象化は、プリミティブ データ型が不十分な場合に言語を拡張するためにプログラマーによって作成されたデータ型です。プリミティブ データ型と同様に、抽象化には、必要な入力とそれらが返す出力をリストする仕様がありますが、仕様はメソッドでプログラマーを圧倒しません。関数、および入力の操作に使用される変数。クラスは抽象化の一例です。API は抽象化の別の例です。」

「カプセル化とは、抽象データ型 (つまり、クラス) を互いに分離した状態であり、メソッド、関数、および変数が互いに競合しないようにするため、プログラマーは他のプログラムで既存のクラスを簡単に再利用できます。そのため、プログラムの残りの部分に干渉します (プログラマーが必要な入力を正しく提供し、返されるデータを正しく処理すると仮定します)。」

私のプロジェクトは ES6 (webpack + babel) です。Platoは素晴らしいですが、ES6 ではまだ動作しません。escomplexと一連の関連パッケージを見てみましたが、作者はこれを保守していないようで、とにかく ES6 をサポートしていないようです。

私はESLint 複雑性ルールを使用して、少なくとも問題がある場合に警告します (6 で警告するように設定されています) が、きれいなレポートと同じではありません。

助言がありますか？

質問 - answer(document, searchTerms) という関数を作成します。この関数は、指定されたすべての検索用語を含む、ドキュメントの最短のスニペットを返します。検索語は任意の順序で表示できます。

以下の私のプログラムは正しい答えを出していますが、デカルト積を行っているため、時間の複雑さが非常に高くなります。入力が非常に高い場合、それらのテスト ケースをクリアできません。このプログラムの複雑さを軽減することはできません。助けていただければ幸いです。ありがとう

誰かが私のプログラムを複製したい場合は、ここにコードがあります

n x mスケーラブルなマトリックスを処理する必要があるアルゴリズム。たとえば、2、1、4 の値を含む 3 秒の時系列があります。3 x 4行列を取得するために分解する必要があります。ここで、3 は時系列の要素の数、4 は最大値です。結果のマトリックスは次のようになります。

これは悪い解決策ですか、それとも単にデータ入力の問題と見なされますか? 質問は、

値を失うことなく、さまざまな要素のマトリックスの各行から情報を配布する必要がありますか?

通常、LOC は、プログラムのソース コードを測定するために広く使用されている指標の 1 つです。Java または C コードのサイズを測定するのに最適です。ただし、現在の研究プロジェクトの 1 つでは、XML ファイル内のコードのサイズを測定する必要があります。XML 形式の柔軟性のため、LOC はこの目的には適していないようです。

XML コードのサイズや複雑さを測定する良い方法はないかと考えていました。私はオンラインで検索しましたが、公開された研究のほとんどは、XML ファイルではなく、XML スキーマ (DTD) の複雑さを定義することに焦点を当てています。例: XML ドキュメント コレクションのメトリック

また、さまざまなタグ名に基づいてノードまたは要素をカウント/リストできるツール/ライブラリがあることもわかりました。例: xml ファイル内の要素数のカウント とXML ノード数を取得する最も簡単な方法

ただし、私たちの研究では、タグや要素の名前は気にしません。XML ファイル、特に Android レイアウト ファイルと AndroidManifest.xml ファイルのコードのサイズや複雑さを測定するには、明確に定義されたメトリックのみが必要です。

受け取った課題に問題があり、問題のテキストに欠陥があると確信しています。私はこれを次のように翻訳しました：

{1,2,..,m}、m < n の要素を持つリスト x[1..2n] を考えてみましょう。すべての要素が単一のペアに存在するように、要素をペア (i < j の (x[i],x[j]) のペア) にグループ化する O(n) の複雑さを持つアルゴリズムを Python で提案および実装します。 . ペアの各セットについて、ペアの最大合計を計算し、それを残りのセットと比較します。それらの最小値を持つセットを返します。

不思議に思う点は以下のとおりです。

• 表内容定義の要素があると言う1..2n, from {1..m}, m < n。しかし、 の場合m < n、一部を複製せずにリストに入力するのに十分な要素がありません。これは許可されていません。それで、私は仮定しm >= 2nます。また、この例ではn = 21より大きい要素を使用していますが、それが意味していると思います。

• O（n）の複雑さ？それらを単一のループに結合する方法はありますか？何も考えられません。

私の計算:

したがって、明らかに、ブルートフォースを使用して、それが有効かどうかを判断することはできません。可能な方法の合計を計算するために使用した式は次のとおりです。

質問：

この問題は間違って書かれており、解決できませんか? もしそうなら、それを実現可能にするために、どのような条件を追加または削除する必要がありますか? Python でいくつかのコードを提案する場合は、事前に作成された関数を使用できないことを覚えておいてください。ありがとうございました

EclipseSDK 3.8.1 で cobertura ツールを使用しています。カバレッジを実行することはできますが、このツールを使用してコードの複雑さをチェックするオプションはありますか? 表示できるのはコード カバレッジだけです。