問題タブ [complexity-theory]

言語設計について私が行った議論によると、多くの人が「1 つの真の言語」は存在せず、今後も存在しないと主張しているようです。これらの人々によると、別の方法は、いくつかの言語に精通し、仕事に適したツールを選択することです。 これは、非常に狭く明確に定義されたインターフェースを介してプロジェクトの残りの部分とやり取りするだけでよいプロジェクト全体または大規模なサブプロジェクトのレベルで完全に理にかなっています。

一方で、多くの小さなサブ問題をエレガントに解決しようとすると、多くの異なる言語を使用することは非常に厄介なことのように思えます。言い換えれば、IMHO、すべてに適した汎用言語は依然として重要です。些細な例として、次のことを行う必要があるとしましょう。

1. ファイルから任意の形式で一連のデータを読み取ります。エラーなどがないかチェックしてください (Perl などで行うのが最適です)。
2. このデータを行列にロードし、一連のハードコアな行列演算を実行します (Matlab などで行うのが最適です)。
3. その上で、高速でスペース効率の高いカスタムの計算集約型ルーチンを実行します (C または C++ で実行するのが最適です)。

これはかなり単純なプロジェクトであり、計算量の多いカスタム マトリックス処理ルーチンを作成することを除けば、どの言語を使用するかについての唯一の適切な答えは、すべてにおいてまともな汎用言語であるように思われます。

ここで何が欠けていますか？複数の言語を効果的に使用して、それぞれの長所を活用するにはどうすればよいでしょうか?

コードの時間/空間の複雑さを検証するために単体テストを使用する人はいますか?

正式な定義はできるだけ少なく、簡単な数学を好む.

かなり一般的な質問があります。プログラマーとしての学校を除いて、アルゴリズムの複雑さを実際に計算する必要があったことはありますか？そして、もし..例を教えていただけませんか。

ありがとうございました ：）

小規模なプロジェクトを扱う場合、データを単純なテキスト ファイルやハッシュ テーブルなどに保存する場合と、実際のデータベースを使用する場合の損益分岐点はどこだと思いますか? シンプルなデータ管理要件を持つ小規模なプロジェクトの場合、実際のデータベースは不要な複雑さであり、YAGNI に違反します。ただし、ある時点で、データベースの複雑さに見合うだけの価値があることは明らかです。問題が単純なアドホック手法には複雑すぎて、実際のデータベースが必要であることを示す兆候は何ですか?

注: エンタープライズ環境に慣れている人にとって、これはおそらく奇妙な質問のように聞こえるでしょう。しかし、私の問題領域はバイオインフォマティクスです。私のプログラミングのほとんどはプロトタイプであり、製品コードではありません。私は主にドメインの専門家であり、副次的にプログラマーです。私のコードのほとんどはアルゴリズム中心であり、データ管理中心ではありません。この質問の主な目的は、通常使用するアドホックな手法ではなく、コードで適切なデータベースを使用することを学ぶと、長期的にどれだけの作業を節約できるかを把握することです。

問題は次のとおりです。

正の整数の集合 { a1 , a2 , a3 , ... , an } が与えられ、その中に同じ数が存在しない (a1 は一度しか存在しない、a2 は一度しか存在しない、...) 例: A = {12 , 5 、7、91}。問題: A の 2 つの素集合 A1 = { b1,b2,...,bm } と A2 = { c1,c2,...,ck} があり、b1+b2+...+bm = c1+ c2+...+ck ?

次の点に注意してください: A1 と A2 が A をカバーすることは必須ではないため、問題が自動的に部分和問題に還元されることはありません。例: A = {2,5,3,4,8,12} A1= {2,5} したがって、A1 の合計は 7 A2= {3,4} したがって、A2 の合計は 7記述されたプロパティなので、問題は解決されます。

どうすればこの問題を解決できますか? 可能なすべての (互いに素な) サブセットを見つけて、それらの合計を計算し、2 つの等しい合計を見つけるよりも良いことはできますか?

お時間をいただきありがとうございます。

さまざまなC++辞書の実装（マップ、辞書、ベクトルなど）についてレポートを作成しています。

std :: mapを使用した挿入の結果は、パフォーマンスがO（log n）であることを示しています。パフォーマンスにも一貫したスパイクがあります。何が原因なのか100％わかりません。それらはメモリ割り当てが原因だと思いますが、これを証明するための文献やドキュメントを見つけることができませんでした。

誰かがこの問題を解決したり、私を正しい方向に向けたりできますか？

乾杯。

次のコードの時間計算量を計算する必要があります。

O(n^2)ですか？

次の時間と空間の複雑さは何ですか:

n の値が 1 になるまで n の値を 1 ずつ減らして再帰的に実行され、m の値を 1 減らすか、m が 1 の場合は 1 を返します。

複雑さはnとmの両方に依存すると思うので、おそらくO（n * m）です。

各ノードが最大で 3 つの子と 3 つの親を持つ *n サイズの多頭非巡回グラフが与えられた場合、2 つのノードが同じ値を共有しない n 長のパスが存在するかどうかを識別する非指数アルゴリズムはありますか?セットの値は説明されますか?

基本的に、各スペースにランダムな値 (1..n) を持つ n*n 迷路があります。すべての値を含む n ノードの (上から下への) パスを見つける必要があります。

現在、深さ優先検索を使用していますがT(n) = 3T(n-1) + O(1)、それはO(3^n)理想的ではない解決策です。

私の恐れを確認するか、正しい方向に向けていただければ幸いです。

編集：これをもう少し具体的にするために、ここに解決策のある迷路があります（深さ優先の解決策を使用して解決されます）。