問題タブ [time-complexity]

分散ファイルシステムでのファイルの可用性の数学的モデルを構築しようとしています。この質問をMathOverflowに投稿しましたが、これはCS質問として分類される可能性もあるので、ここでも試してみます。

システムは次のように機能します。ノードは、r * bリモートノードにファイル（イレイジャーコードを使用してエンコード）を格納します。ここで、rはレプリケーション係数、bは整数定数です。イレイジャーコーディングされたファイルには、少なくともb個のリモートノードが使用可能であり、ファイルの一部を返す場合にファイルを復元できるという特性があります。

これに対する最も簡単なアプローチは、すべてのリモートノードが互いに独立しており、同じ可用性pを持っていると想定することです。これらの仮定では、ファイルの可用性は二項分布に従います。

残念ながら、このペーパーで示されているように、これら2つの仮定は、無視できないエラーを引き起こす可能性があります： http ://deim.urv.cat/~lluis.pamies/uploads/Main/icpp09-paper.pdf 。

すべてのノードが同じ可用性を持っているという仮定を克服する1つの方法は、利用可能な/利用できないノードの可能な各組み合わせの確率を計算し、これらすべての結果の合計を取得することです（これは、上記の論文で示唆されているようなものです。私が今説明したものよりも正式に）。このアプローチは、深さr * bの二分木として見ることができ、各リーブは、使用可能なノードと使用できないノードの1つの可能な組み合わせです。ファイルの可用性は、>=bの使用可能なノードで休暇に到達する確率と同じです。このアプローチはより正確ですが、計算コストは​​です。また、ノードの独立性の仮定は扱いません。

二項分布近似よりも誤差が少なく、計算コストが優れている、優れた近似のアイデアはありますか？

各ノードのavailability-dataは、で構成されるタプルのセットであると想定できます(measurement-date, node measuring, node being measured, succes/failure-bit)。このデータを使用して、たとえば、ノード間の可用性と可用性の分散の相関関係を計算できます。

私は一度次の引用を聞いたが、それが誰に起因するのかを忘れた：

（多項式時間）アルゴリズムが停止するのを待っている間、あなたの寿命も多項式によって制限されることを忘れないでください。

誰かが参照を提供できますか？

私が持っている別の質問は次のとおりです。多項式時間アルゴリズムは素晴らしいですが、実際に使用されるアルゴリズムの例は何O(n^101)ですか？つまり、高度な多項式に制限されていますか？

これはしばらくの間私の心に残っている質問です...

アイテムのリストとそれらの同値関係があり、2つのアイテムの比較には一定の時間がかかるとします。アイテムのパーティション、たとえばリンクリストのリストを返したいのですが、それぞれに同等のアイテムがすべて含まれています。

これを行う1つの方法は、同等性をアイテムの順序付けに拡張し、それらを（並べ替えアルゴリズムを使用して）順序付けすることです。その後、すべての同等のアイテムが隣接します。

しかし、それはソートよりも効率的に行うことができますか？この問題の時間計算量は、並べ替えの時間計算量よりも低いですか？そうでない場合は、なぜですか？

O（1）での実装HashSet.ElementAtですか？そうでない場合、それは何ですか？

NxNルームとして組織された博物館があります。一部の部屋は施錠され、アクセスできません。他の部屋は開いていて、警備員がいる部屋もあります。警備員は東西南北にのみ移動でき、開いた部屋と博物館内でのみ移動できます。各部屋について、警備員までの最短距離を見つけます。アルゴリズムの時間計算量は?

ビッグ O 表記の概念を理解するのに苦労しました。したがって、定義によるビッグ O は次のようになりT(n) ∈ O(G(n)) if T(n) <= G(n) * Cます。

定数 "C" は 0 より大きい任意の整数にすることができるため、次の例も当てはまりませんか?

例：

ここで、C は n の値に等しくなります。

答えがそれであることは知っていますがn log n ∉ O(log n)、C は任意の定数になる可能性があるため、その方法がわかりません。

あなたの助けを前もってありがとう:D

複雑な多角形の凸包を見つけるための最悪の O(n log n) アルゴリズムと、単純な多角形の凸包を見つけるための最悪の O(n) アルゴリズムがあることは知っています。複雑な多角形の凸包を見つけるための最悪の O(n) アルゴリズムはありますか?

複雑な多角形は、線分が交差する可能性がある多角形です。複雑な多角形の凸包を見つけることは、点の順序付けられていないリストの凸包を見つけることと同じです。

forと交換a[i,j]する（指定された行列を転置する）このコードの時間計算量はどれくらいですか？a[j,i]j > i

為に

は

両方を n で割ってみました。

しかし、どちらがより速く成長するかはまだわかりません。誰かがこれについて私を助けて、答えの理由を説明できますか? どちらがより速く成長するかを（電卓なしで）どのように判断できるかを本当に知りたいです。

これは非常に有名な多国籍企業から私に尋ねられた質問です。質問は次のとおりです...

0と1の2DN*N配列を入力します。A（i、j）= 1の場合、i番目の行とj番目の列に対応するすべての値は1になります。すでに1がある場合は、1のままです。

例として、配列がある場合

次のように出力を取得する必要があります

入力行列はまばらに入力されています。

これはO（N ^ 2）未満で可能ですか？

別の条件で、追加のスペースが提供されていません。スペース<=O（N）を使用して複雑さを実現する方法があるかどうかを知りたいです。

PS：O（N * N）の複雑さを与える答えは必要ありません。これは宿題の問題ではありません。私は多くのことを試みましたが、適切な解決策を得ることができず、ここでいくつかのアイデアを得ることができると思いました。複雑さのために印刷を脇に置いておきます

私の大まかなアイデアは、通過する要素の数を動的に排除して、それらを約2N程度に制限することでした。しかし、私は適切なアイデアを得ることができませんでした。