問題タブ [complexity-theory]

シンプルに保つことは誰もが知っていますよね？

システム間の相互作用の数として複雑さが測定されるのを見てきました。直感以外に、特定の設計またはソフトウェアの複雑さのレベルを判断するために使用できる (できればより客観的な) 方法は何ですか?

あなたの好きなルールやヒューリスティックは何ですか?

コンピュータ科学者が「ナイーブな実装」を意味することの最も明確な説明は何ですか? 単純な実装が技術的には問題の機能的な解決策になる可能性があるが、実際にはまったく使用できないことを (理想的には、技術者ではない人にも) 説明する明確な例が必要です。

Webから情報をマイニングするためのツールを構築しています。いくつかの作品があります。

• Webからデータをクロールする
• テンプレートとビジネスルールに基づいて情報を抽出する
• 結果をデータベースに解析します
• 正規化とフィルタリングのルールを適用する
• 等

問題は、問題のトラブルシューティングと、各段階で何が起こっているのかを「高レベルで把握」することです。

複雑なプロセスを理解して管理するのにどのようなテクニックが役立ちましたか？

• WindowsWorkflowFoundationなどのワークフローツールを使用する
• 個別の関数をコマンドラインツールにカプセル化し、スクリプトツールを使用してそれらをリンクします
• ドメイン固有言語（DSL）を記述して、より高いレベルで発生する順序を指定します。

相互作用する多くのコンポーネントを備えたシステムをどのように処理するのか興味があります。ソースコードをトレースするよりも高いレベルでシステムがどのように機能するかを文書化/理解したいと思います。

数学のバックグラウンドがあると仮定して、計算複雑性理論の一般的な概要を素朴な人にどのように説明しますか?

P = NP の質問の説明を探しています。Pとは？NPとは？NPハードとは？

ウィキペディアは、読者が関連するすべての概念をすでに理解しているかのように書かれていることがあります。

実用的な量子コンピューティングが実現した場合、整数因数分解や離散対数ではなく、NP 完全問題に基づく公開鍵暗号アルゴリズムが存在するかどうか疑問に思っています。

編集：

量子コンピューターに関する wiki 記事の「計算複雑性理論における量子コンピューティング」セクションを確認してください 。 量子コンピューターが解決できる問題のクラス (BQP) は、NP 完全よりも厳密に簡単であると考えられていることを指摘しています。

編集2：

「NP完全に基づく」は、私が興味を持っていることを表現する悪い方法です.

私が求めようとしていたのは、暗号を破るためのあらゆる方法を使用して、根底にある NP 完全問題を破ることができるという特性を持つ公開鍵暗号化アルゴリズムです。これは、暗号を破ると P=NP が証明されることを意味します。

最悪の場合の時間複雑性 t(n) とは何ですか :- アルゴリズムに関するこの本を読んでいます。例として、T(n) を取得する方法 .... 選択ソート アルゴリズムのように

selectionSort(A[0..n-1]) を扱っているかのように

疑似コードを書いてみましょう

--------C#でも書きます---------------

==================

t（n）を取得する方法、または既知の最悪の場合の時間の複雑さ

ハッシュと検索のタイプ​​を含むアルゴリズムの議論で、O（1）の非常に奇妙な使用法に気づきました。多くの場合、言語システムによって提供される辞書タイプを使用するか、配列を使用して使用される辞書またはハッシュ配列タイプを使用します。 -インデックス表記。

基本的に、O（1）は、一定の時間と（通常は）固定された空間によって制限されることを意味します。いくつかのかなり基本的な操作はO（1）ですが、中間言語と特別なVMを使用すると、ここで考えるものが歪む傾向があります（たとえば、ガベージコレクターやその他の動的プロセスをO（1）アクティビティよりもどのように償却するか）。

しかし、レイテンシーの償却やガベージコレクションなどを無視すると、非常に特殊な条件下を除いて、ある種の検索を含む特定の手法がO（1）になる可能性があるという仮定への飛躍がどのように行われるのかまだわかりません。

これは以前にも気づきましたが、Pandincusの質問に、「C＃.NETでO（1）時間にアイテムを取得するために使用する「適切な」コレクション？」という例が表示されました。。

そこで述べたように、保証された境界としてO（1）アクセスを提供するコレクションは、整数のインデックス値を持つ固定境界配列だけです。配列は、O（1）操作を使用してそのインデックスを持つセルを見つけるランダムアクセスメモリへのマッピングによって実装されていると想定されます。

別の種類のインデックス（または整数インデックスを持つスパース配列）の一致するセルの場所を特定するための何らかの検索を伴うコレクションの場合、人生はそれほど簡単ではありません。特に、衝突があり、混雑が発生する可能性がある場合、アクセスは正確にはO（1）ではありません。また、コレクションに柔軟性がある場合は、輻輳が緩和される（たとえば、衝突の発生率が高い、ツリーの不均衡など）基礎となる構造（ツリーやハッシュテーブルなど）を拡張するコストを認識して償却する必要があります。

私はこれらの柔軟で動的な構造をO（1）として話すことを考えたことはありませんでした。それでも、実際にO（1）アクセスを保証するために維持する必要のある条件を特定せずに、O（1）ソリューションとして提供されていると思います（また、その定数は無視できるほど小さいです）。

質問：この準備はすべて、本当に質問のためのものです。O（1）の周りのカジュアルさは何ですか、そしてなぜそれはそれほど盲目的に受け入れられるのですか？O（1）でさえ、ほぼ一定であっても、望ましくないほど大きくなる可能性があることは認識されていますか？それとも、O（1）は、計算の複雑さの概念を非公式な使用に単純に流用しているのでしょうか。困惑しています。

更新：回答とコメントは、私がO（1）を自分で定義することに何気がなかった場所を指摘しており、それを修復しました。私はまだ良い答えを探しています、そしていくつかのケースでは、コメントスレッドのいくつかは彼らの答えよりもかなり面白いです。

Big-O 表記法は理解できますが、多くの関数で計算する方法がわかりません。特に、単純なバージョンのフィボナッチ数列の計算上の複雑さを理解しようとしています。

フィボナッチ数列の計算上の複雑さとはどのように計算されますか?

REXXのlength（）関数の処理オーバーヘッドは、文字列の長さによってどのように変化しますか？

更新：私は使用しています：

• uni-REXX（R）バージョン297t
• Open-REXX（TM）Copyright（C）iXCorporation1989-2002。全著作権所有。

重複するデータのセット間の共通点と相違点を識別するのに役立つアルゴリズムに関する情報が欲しいです。

例として、stackoverflow のタグ システムを使用します。

この質問に 5 つのタグが付けられたとします。これらのタグの少なくとも 1 つを持つ他の 1000 の質問があるとします。これらの 1000 の質問のうち、元の投稿にはないタグが共通している質問はいくつありますか?

これを説明するもう 1 つの簡単な方法は、自動提案タグ付けシステムです。

「[選択した 5 つのタグ] で質問にタグを付けました。他の同様の質問には [関心がある可能性のあるタグのリスト] がタグ付けされました。[関心がある可能性のあるタグのリスト] は、頻繁に発生するタグで私の元のリスト。

可能であればC#でのコード例:)