問題タブ [time-complexity]

問題 P が NP-Complete であることを証明するには、既知の NPC 問題を P に還元する必要があると思っていましたが、独立集合問題の解を見ると、そうではないようです。

独立集合が NP 完全であることを証明するには、グラフ G を取り、その逆 G' を見つけ、CLIQUE(G') を計算します。しかし、これは逆のことをしています: それが NPC かどうか PI DON'T がわからない問題を取り上げ、それを既知の NPC 問題に減らします。

ソリューションの例を次に示します。

ここで何が欠けていますか？やり方が逆だからまずいんじゃないの？

ウィキペディアから：

ソートされたリストの実装: スーパーマーケットのレジの列のように、重要な人々が重要でない人々の前で「カット」する場所。( O(n) の挿入時間、O(1) の get-next 時間、O(n*log(n)) のビルド)

二分探索アルゴリズムで挿入位置を検索すると、挿入時間の複雑さは O(log(n)) になるはずです。ここでは、ジョブの到着順序を優先順位の要素として扱います。

それで、私は間違っていますか、それともウィキペディアは間違っていますか?

更新:TAOCP のリストの厳密な定義によると:

線形リストは、n >=0 のノード X 1、X[2]、...、X[n] のシーケンスであり、その基本的な構造特性には、アイテムが行に表示されるときのアイテム間の相対位置のみが含まれます。

ウィキペディアの参照リストはlinked-listではなく、 arrayである可能性があると思います。

ありがとう。

ArrayListjavaの配列またはリストですか? get 操作の時間計算量はどれくらいですO(n)かO(1)?

おそらくコンパイラの理解が不足しているために、私はいつもこれについて少し混乱してきました。しかし、例としてPythonを使用してみましょう。numlistと呼ばれる数値の大きなリストがあり、重複を取り除きたい場合は、リストで集合演算子（set（numlist）の例）を使用できます。その見返りに、私たちは私たちの番号のセットを持っているでしょう。私の知る限り、この操作はO（n）時間で実行されます。この操作を処理するために独自のアルゴリズムを作成する場合でも、私がこれまでに期待できる最高のものはO（n ^ 2）です。

私が得られないのは、set（）のような内部操作が言語アルゴリズムの外部よりもはるかに高速になることを可能にするものです。まだチェックが必要ですね。

次のコードスニペットがあります。

複雑さはO(n^2)ですが、内部ループの複雑さについてもう少し掘り下げたい場合は、それでしょう(n (n-1))/2か(n-1)!？

最近、私は次のようなセミナー作品を読みました。

[一般的なグラフの] マッチング アルゴリズムは、重み付きの場合に拡張できます。これは、多項式時間で解くことができる「最も難しい」組み合わせ最適化問題の 1 つと思われます。

すぐに次の疑問が頭に浮かびました。

他の「P-hard」問題を知っていますか?

今のところ、P-hard を次のように定義したいと思います。(または、多項式時間で問題を解決する決定論的アルゴリズムが既にある場合、どのように「ハード」をより適切に定義できますか?)

Big O Notation の実行時間と償却時間について学習しています。O(n)線形時間の概念を理解しています。つまり、入力のサイズがアルゴリズムの成長に比例して影響することを意味します...たとえば、二次時間O(n ² )などについても同じことが言えます.アルゴリズムでさえ階乗によって成長するO(n!)回の順列ジェネレーターなど。

たとえば、アルゴリズムは入力nに比例して大きくなるため、次の関数はO(n)です。

同様に、ネストされたループがある場合、時間は O(n ² ) になります。

しかし、O(log n)とは正確には何ですか? たとえば、完全な二分木の高さがO(log n)であるとはどういう意味ですか?

_{log 10} 100 = 2という意味で、対数が何であるかは知っていますが（詳細ではないかもしれませんが）、対数時間で関数を特定する方法がわかりません。

ウィキペディアの素集合フォレストの和集合/検索アルゴリズムの内訳は次のとおりです。

• ばらばらなばらばらの森... ( O(n))
  • ... ランクごとに結合 ... (現在は に改善O(log(n))
    • ...パス圧縮あり（現在O(a(n))、効果的に に改善されていますO(1)）

ランクによる結合を実装するには、各ノードがrank比較のためにフィールドを保持する必要があります。私の質問は、ランクによる結合はこの追加スペースの価値があるかということです? ランクによる結合をスキップして、代わりにパス圧縮を行うとどうなりますか? それは十分ですか？現在の償却複雑度は?

O(log(n)パス圧縮 (償却された複雑さ) のないランクによる結合は、ほとんどの実用的なアプリケーションに十分であることを意味するコメントが作成されます。正解です。私が求めているのは逆です: ランクによるユニオンをスキップして、代わりにパス圧縮のみを行うとどうなりますか?

ある意味で、パスの圧縮は、ランクごとの結合を改善するための追加の手順であり、そのため、その追加の手順を省略しても悲惨な結果を招くことはありません。しかし、ランクによる結合はパス圧縮に必要な中間ステップですか? それをスキップして直接パス圧縮に進むことはできますか?

また、ランクによる結合がなければ、結合が繰り返されると連結リストのような構造が作成される可能性があることも指摘されました。これは、単一パスの圧縮操作がO(n)最悪の場合にかかる可能性があることを意味します。もちろん、これは将来の運用に影響を与えるため、多くの運用で償却したときにこれがどのように機能するかが、私がより興味を持っていることです.

先週、著者が 2 ページ目に言及しているこの論文に出くわしました。

これにより、整数のエッジの重みに対して線形の実行時間が得られることに注意してください。

3 ページ目も同様です。

これにより、整数エッジ重みの線形実行時間と、比較ベースの並べ替えの O(m log n) が得られます。

そして8ページ目：

特に、高速整数ソートを使用すると、おそらく GPA が大幅に高速化されます。

これは、整数値の特別な状況下で O(n) ソート アルゴリズムがあることを意味しますか? それともグラフ理論の専門ですか？

PS:
最初のページで次のように述べているため、参考文献 [3] が役立つ可能性があります。

[..] 整数エッジ重み [3]、[...] などの [..] グラフ クラスのさらなる改善

しかし、どの科学雑誌にもアクセスできませんでした。

乗算、平方根、対数、スカラー、行列積などの基本的な算術演算の広範なアルゴリズムのBig-Oの複雑さは何ですか？

Big-Oの複雑さの点ではより効率的であるが、実際のソリューションではあまり普及していない（たとえば、一般的なソフトウェアライブラリに実装されていない）エキゾチックなアルゴリズムはありますか？