問題タブ [complexity-theory]

3つのNP完全問題を埋め込みたい（そのうちの2つはNP完全であることがわかっており、1つは私自身の考えです）。私は「この質問」を見て、埋め込みの問題を理論的に再解釈することについて考えました。

• ウェイターは泥棒です。
• テーブルは店です。
• 食品は重量の異なる大切なものです。
• 泥棒は強盗の前にすべてのアイテムの価格と重量を知っています。
• 彼の目標は、最も効率的な強盗（使用されるナップザックの最大容量、最も価値のあるアイテムを入手）であり、すべての店舗を強盗（少なくとも1つのアイテムを入手）します（強盗ツアーを完了するための最短の方法、各店舗を1回訪問します）。

この部分は2つのNP完全問題を埋め込んでいます。

私の考えは、アイテムが多いほどバッグの重量が増えるということです。バッグの重量が増えると、泥棒は指数関数的に遅くなります。したがって、泥棒のもう1つの標的は、できるだけ早く強盗を終わらせることです。

現時点では、私のアイデアが実際にNP完全であるかどうかはわかりません。たぶん、「重力」はNP完全問題だけではありません。しかし、おそらくそれは巡回セールスマン問題とナップサック問題のこの文脈にあります。

だから私の質問は：

1. 泥棒のNP完全問題の減速も完了していますか？

2. これらの3つの埋め込まれた問題を単純なNP完全問題に減らすことは可能ですか？

私は今日、これまでに作成された中で最も複雑で印象的なアプリケーションが何であるかについて考えていました。それで、私は自分が何に慣れていて、毎日データベースを使用しているのかを考え始めました。

それから私は未知の分野（私たちのほとんどにとって私が推測する）、政府に入りました。火星のローバーと通信できるNASAアプリケーションの複雑さを想像することしかできません。

でもそれから、子供の頃から毎日使っているもの、ゲームについて考え始めました。ゲーム開発者ではないので、これは私が考えることができるものを超えるAIと計算の複雑さについての膨大な量の質問を私の想像にもたらしました。

ゲームは最も複雑で印象的なアプリケーションですか？

次の複雑さは何ですか:

O（n ^ 2）であることは知っていますが、これをどのように計算しますか？なぜ n*log n ではないのでしょうか?

コードが何をしているのかを理解するためにコードをステップ実行するために、作業している言語のデバッガーを使用しますか? それとも、他の人が書いたコードを見て、何が起こっているのかを理解するのは簡単だと思いますか? C# で記述されたコードについて話していますが、どの言語でもかまいません。

ある質問にインタビューされたばかりですが、答えはどうあるべきか知りたいです。問題は、本質的に次のとおりでした。

n個の整数のソートされていないリストがあるとします。このリストでk個の最小値をどのように見つけますか？つまり、[10、11、24、12、13]のリストがあり、2つの最小値を探している場合は、[10、11]が得られます。

私はO（n * log（k））ソリューションを持っており、それが私の最善ですが、他の人が何を思いついているのか興味があります。私は自分の解決策を投稿することで人々の脳を汚染することを控え、しばらくしてそれを編集します。

編集＃1：たとえば、次のような関数：list getMinVals（list＆l、int k）

編集＃2：それは選択アルゴリズムのように見えるので、私も自分のソリューションを投入します。リストを反復処理し、優先キューを使用して最小値を保存します。優先度付きキューの仕様では、最大値が優先度付きキューの一番上になるため、一番上を要素と比較すると、一番上がポップされ、小さい方の要素がプッシュされます。これは、優先キューにO（log n）プッシュとO（1）ポップがあることを前提としています。

結果のO表記と分析方法の独自性の両方に関して、驚くべき（タフで奇妙な）複雑さ分析を持っていると思うアルゴリズムはどれですか？

ブール値の充足可能性がNP完全であることは知っていますが、ブール式の最小化/単純化です。これは、特定の式を記号形式で取得し、同等であるが単純化された式を記号形式で生成することを意味します.NP完全ですか？充足可能性から最小化への減少があるかどうかはわかりませんが、おそらくあると思います。誰かが確かに知っていますか？

ソフトウェアの設計担当者は、非常に複雑なアーキテクチャを思いつきます。

ユーザーが決して知らない難解な機能をすべて備えていて、すべての雑誌の記事が最新のクールなことだと言っていることをしているときにその達成感を得るのは、すべて問題なくダンディーですが、私たちはお金を費やすつもりです.私たちの巧妙さの記念碑であるエンジニアリング時間の半分であり、ユーザーが必要とする実際の製品ではなく、上層部の経営陣が合理的な、または少なくとも制限された時間枠内で完了することを期待しています。

そして、時間がなくなり始めたとき、つまりその機会があれば、とにかく単純なソリューションに戻らなければならないでしょう.

Keep It Simple, Stupid™ というフレーズを聞いたことがあるでしょう。

チーム内の過度の複雑さとどのように戦っていますか?

私が最近繰り返し取り組んだ例の 1 つは、RDBMS ではなく、完全に非正規化されたデータベース設計に移行するという決定が下されたときです。「速いから！」完全に非正規化されたデータベースを正しく作成するのは非常に難しく、Flickr や ebay などの非常に特殊なデータの問題にのみ適しています。また、開発の残りの部分に比べて開発者の時間が非常に高くなる可能性があります。

タイトル付きの配列を使用しています。各タイトル インデックスは、そのタイトルの html を含むデータベース内の ID に対応します。

タイトルの 1 つを含む文字列があるとします。

文字列「タイトル」を使用して対応する ID を取得するには、次のようにします。

私が使用できる別の方法は、titles の正反対である titles 配列と共に連想配列を作成することです。つまり、文字列をインデックスとして使用し、数値を返します。

次に、次の方法で ID にアクセスできます。

CPU、メモリなどを考慮すると、何が最も効果的でしょうか?

また、私の論理がすべて間違っている場合はお知らせください。

ありがとうウィレム

最悪の場合の時間の複雑さを与える方法を見つけようとしています。私の分析についてはよくわかりません。ネストされたforループの大きな Oを読みましたn^2。内部にforループがあるループの場合、これは正しいですか?while

これまでのところ、私は持っています:

しかし、最悪の場合の時間の複雑さを分析するため にwhileandループの中に入る必要があるかどうかはわかりません...for

ここで、それがしっかりと束縛されていることを証明する必要があります。それがビッグ シータです。

ネストされたforループには Big O of があることを読みましたn^2。これはビッグシータにも当てはまりますか? そうでない場合、ビッグシータを見つけるにはどうすればよいでしょうか?!

**C1= C sub 1、C2= C sub 2、および no= n naught すべて正の実数の要素です

を見つけるためT(n)に、値をj調べ、while ループが実行された回数を調べました。

分析:
while ループの実行の合計を取得し、(n(n+1))/2 これを my として割り当て、T(n)によって厳密に制限されていることを証明しn^2ます。あれはn(n+1)/2= θ(n^2)

スクラッチワーク:

PF:

1. 0 ≤ C1(n^2) が真であることを示す C1(n^2)= n^2/2
   n^2/2≥ no^2/2
   ⇒no^2/2≥ 0
   1/2 > 0
   よって C1 (n^2) ≥ 0 は真であることが証明されています!

2. C1(n^2) ≤ (n(n+1))/2 が真であることを示す C1(n^2) ≤ (n(n+1))/2
   n^2/2 ≤ (n(n+1) ))/2 n^2 ≤ n(n+1)
   n^2 ≤ n^2+n
   0 ≤ n

   n ≥ no = 1 であるため、これは正しいことがわかっています。
   したがって、C1(n^2) ≤ (n(n+1))/2 は正しいことが証明されています。

3. (n(n+1))/2 ≤ C2(n^2) が真であることを示します (n(n+1))/2 ≤ C2(n^2)
   (n+1)/2 ≤ C2(n)
   n+1 ≤ 2 C2(n)
   n+1 ≤ 2(n)
   1 ≤ 2n-n
   1 ≤ n(2-1) = n
   1≤ n
   また、n ≥ no = 1 なので、これが真であることがわかっています。

   したがって、1、2、および 3 により、
   0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2( n^2) すべての n ≥ no

皆さんのことを教えてください... 私はこの資料を理解しようとしており、皆さんの意見を求めています!