問題タブ [complexity-theory]

Aho、Hopcroft、Ullman の「データ構造とアルゴリズム」を読んでいて、演習 1.12 B と混同しています。

この Pascal 手続きの計算量 (Big O 表記で表される) はどれか?

手伝っていただけませんか？

ありがとう！

これはプログラミングの質問よりも複雑さの理論の質問であることを私は知っています。ここに間違ったことを書いていないことを願っています。間違った場所である場合はお詫びしますが、誰かが答えを持っていることを願っています。そして、それは複雑性理論の質問であることによって、どういうわけかプログラムミンに関連しています。

私は線形反復シーケンスを研究していますが、シーケンスのn番目の値を取得するには、コンパニオンマトリックスの累乗を取得する必要があることが表示されたので、累乗を取得するための既知のアルゴリズムがあるかどうか疑問に思いました。この種のマトリックスの高速な方法で..

コーディングの例を示すことはできませんが、もう少し説明してみましょう。

k次の同次線形反復シーケンス：
s（n + k）= a（k-1）s（n + k-1）+ a（k-2）s（n + k-2）+ .. .. + a（0）
for n = 0,1、..ここで、s（i）はシーケンスのi番目の値であり、a（i）は代数フィールドの係数です。

Aは、次の場合の上記のシーケンスのコンパニオン行列です：
（0 0 0 0 ... 0 a（0））
（1 0 0 0 ... 0 a（1））
（0 1 0 0 ... 0 a （2））
（.. .. .. .. .. .. .. .. ..）
（0 0 0 0 ... 1 a（k-1））
さらに、理論では、シーケンスは次のとおりです
。s（n）= s（0）A ^ n for n = 0,1、..
これで、助けてくれてありがとう。

[0..n ^ 3-1]の範囲のn個の整数の入力セットが与えられた場合、線形時間ソートアルゴリズムを提供します。

これは木曜日の私のテストのレビューであり、この問題にどのように取り組むべきかわかりません。

質問正規表現置換の複雑さ は質問に近づいていますが、同じではありません。theprise の返信によると、(DFA エンジンの) 複雑さは次のとおりです。

O(2^m + n) [m は正規表現の長さ、n は文字列の長さ]

15-16 ページの赤い本「アルゴリズム設計マニュアル」では、さまざまなアルゴリズムの時間について説明しています。それによると、アルゴリズムの長さが 1,000,000 を超えると、O(m^2) のアルゴリズムは絶望的です。1ナノ秒の動作時間を想定すると、処理に16.7分かかります。

その本の声明は私の興味を増大させた. 1,000,000 文字の長さの正規表現を 16.7 分の処理時間で実行できますか? 壊滅的な正規表現を実行しても、処理時間は維持できますか? 私は本当にそれを疑います。

多項式時間で 1 ナノ秒の演算時間が可能な最長の正規表現は?

簡単な概要

ナップザック問題について調べてみました

http://en.wikipedia.org/wiki/Knapsack_problem

それが私のプロジェクトに必要なものであることはわかっていますが、プロジェクトの複雑な部分は、メインの袋の中に複数の袋が必要になることです。

すべての「バッグ」を収納できる大きなナップザックは、x 個の「バッグ」しか持ち運べません (例として 9 個としましょう)。各バッグには異なる値があります。

• 重さ
• 料金
• サイズ
• 容量

など、これらの値はすべて整数です。0から100までと仮定しましょう。

内側のバッグにもタイプが割り当てられ、プログラム入力には同じタイプの複数が与えられますが、外側のバッグ内にはそのタイプの 1 つしか存在できません。

メイン バッグが保持できる最大重量を割り当てる必要があり、小さいバッグの他のすべてのプロパティは重み付けされた値でグループ化する必要があります。

例

アウターバッグ:

• 小さめのバッグなら9個収納可能
• 体重が98以下 [ギブオアテイク5]
• 各タイプを 1 つ保持する必要があり、一度に各タイプを 1 つだけ保持できます。

インナーバッグ:

• コスト、100% で加重
• サイズ、加重 67%
• 容量、加重 44%

プログラムには複数のバッグの入力が与えられ、小さなバッグの組み合わせを大きなバッグに入れる必要があります。入力に応じて複数のソリューションがあり、プログラムは最適なソリューションを出力します。

私がこれにアプローチするための最良の方法は何だと思いますか。

JavaまたはC#でプログラミングします。PHP でプログラムしたいのですが、Web サーバーにとってアルゴリズムが非常に非効率的ではないかと心配しています。

あなたが与えることができる助けをありがとう

-ザック

1,000 万人のプレイヤーがいるオンライン ポーカー サイトの共謀検出のアルゴリズムの複雑さを説明する最良の方法は何ですか?

仮定します（これらの仮定は大きな違いを生むとは思わないので、無視してかまいませんが、明確にするために）：

• サイトの登録ユーザー数が 10,000,000 であること。
• これらのプレイヤーが合計 50 億回のハンドをプレイしたこと。
• 提供される唯一の情報は、サイトの「マスターハンド履歴データベース」であり、すべてのプレーヤーのホールカードと各ハンドの賭けアクションが含まれています.
• 言い換えれば、IP アドレスを調べたり、異常なレーキ/利益パターンを探したりするなどの近道をすることはできません。
• ちょうど N 人 (N は 2 から 10 の間) のプレーヤーのグループを渡すと、グループ内のすべてのプレーヤーが共謀した場合に TRUE を返す関数が与えられたと仮定します。すべてのプレイヤーではなく一部のプレイヤーが共謀者である場合、関数は FALSE を返します。TRUE の戻り値は、(たとえば) 75% の信頼度で作成されます。

あなたの仕事は、共謀したすべてのプレイヤーの完全なリストと、彼が共謀したプレイヤーの完全なリストを作成することです。最近、この問題が NP 困難であると説明されているのを耳にしましたが、これは正確ですか? 単に「難しい」ものを「NP」または「NP-hard」と呼ぶことがあります。

ありがとう！

私はデータ マイニング プロジェクトに興味があり、コード レビューが必要な特定のチェックインと不要なチェックインを判断する分類アルゴリズムを作成したいと常に考えていました。

私は自分のアルゴリズムのために多くのヒューリスティックを開発しましたが、まだキラーを理解していません...

コードのチャンクの計算の複雑さをプログラムでチェックするにはどうすればよいですか?

さらに興味深いのは、コードだけでなく、ソース管理リポジトリが提供する差分を使用して、より良いデータを取得するにはどうすればよいかということです..

IE: チェックインしているコードに複雑さを追加すると、残っているコードの複雑さが軽減されますが、それは「良い」コードと見なされるべきではありませんか?

これに関するあなたの考えに興味があります。

アップデート

どうやら私ははっきりしていなかったようです。これ欲しい

double codeValue = CodeChecker.CheckCode(someCodeFile);

コードの良さに基づいて数字を出してほしい。複雑さを計算するときにVS2008が与えるような数値から始めますが、さらにヒューリスティックに移りたいと思います。

誰にもアイデアはありますか？それは大歓迎です！

LIKE最も人気のあるデータベースのSQL演算子の複雑さを知っている人はいますか？

アルゴリズムの最悪の場合の複雑さを判断する方法を誰かに説明してもらえますか? 式 W(n) = max{t(I)|D の I 要素) を使用する必要があることはわかっています。ここで、D はサイズ n の入力のセットです。各要素に対して実行された操作の数を計算し、その最大値を取得しますか? これを達成するためのより簡単な方法は何ですか?