問題タブ [time-complexity]

フルーリーのアルゴリズム (オイラー回路を取得するために使用される) の時間計算量を調べるのを手伝ってくれませんか?

重複の可能性：
プロパティとメソッド

多くの場合、何かがプロパティであるかメソッドであるかは明らかですが、あいまいと見なされる可能性のある項目があります。

明らかなプロパティ：

• "名前"
• "長さ"

明らかな方法：

• "メッセージを送る"
• 「印刷」

あいまい：

• 「有効」/「IsValid」/「検証」
• 「InBounds」/「IsInBounds」/「CheckBounds」
• "AverageChildValue" / "CalcAverageChildValue"
• 「ColorSaturation」/「SetColorSaturation」

あいまいな方法に傾倒すると思いますが、これを決定するのに役立つ規則や規則を知っている人はいますか？たとえば、すべてのプロパティをO（1）にする必要がありますか？プロパティが他のデータを変更できないようにする必要がありますか（ColorSaturationはR、G、B値を変更する可能性があります）？計算や集計がある場合、それはプロパティではありませんか？

学術的な観点からだけで（そしてそれが良い考えだと思うからではありません）、プロパティに夢中にならず、議論をせずにクラスの尋問であるすべてのものを作成する理由があります。単一の引数を持つクラスで失敗することはできません、プロパティ？

何がより高速で、速度を達成するためにLinq標準を犠牲にする必要がありますか（辞書ルックアップが本当に高速であると仮定）？だから私に詳しく説明させてください：

私は次のものを持っています：

シリアル番号などの属性に基づいて商品を検索する必要があります。最初に辞書を作成してから、次のように入力します。

製品を見つけるときは、辞書ルックアップによって提供されるO（1）を利用してください。

または、Linqを使用します。

Dictアプローチの欠点は、もちろん、これにはメモリ内のより多くのスペース、書き込むためのより多くのコード、あまりエレガントではないなどが必要になることです（ただし、これのほとんどは議論の余地があります）。それが要因ではないと仮定します。私は最初のアプローチを取るべきですか？

結論として、上記のLinqアプローチの複雑さが実際にO（n）であるかどうかを確認したいと思いますが、それよりも優れているかどうかはわかりません。

MSDNは、次のSortedSet（T）.Addメソッドを示しています。

Countが内部配列の容量よりも小さい場合、このメソッドはO（1）操作です。

誰かが「どうやって」説明してもらえますか？つまり、新しい値を追加するときは、値を追加する正しい場所を見つける必要があり（別の値と比較して）、内部実装はO（log N）挿入の複雑さを持つ「赤黒木」のように見えます。

無限の数の処理ユニットと無限のスペースが与えられた場合、合理的な時間内に O(n!) の複雑さの問題を解決することは可能ですか?

O(n!) 問題の典型的な例は、すべての順列 (順序付けられた組み合わせ) を試すブルート フォース検索です。

ウィキペディアは次のように述べています。

選択アルゴリズム: ヒープを使用して、最小値、最大値、最小値と最大値の両方、中央値、さらには k 番目に大きい要素を見つけることを線形時間で行うことができます。

それが言っているのは、それができるということだけであり、方法ではありません。

ヒープを使用してこれを行う方法を教えてください。

ウィキペディアから：

アルゴリズムの複雑さは O(n(logn)(loglogn))ビット演算です。

どうやってそこにたどり着きますか？

複雑さにこのloglogn用語が含まれているということは、sqrt(n)どこかにあることを私に教えてくれます。

最初の100個の数値（n = 100）でふるいを実行していると仮定します。数値を複合としてマークするのに一定の時間がかかると仮定すると（配列の実装）、使用する回数は次のmark_composite()ようになります。

そして、次の素数を見つけるために（たとえば、7の倍数であるすべての数を取り消した後にジャンプするために5）、操作の数はになりますO(n)。

したがって、複雑さはになりますO(n^3)。同意しますか？

私が行っているこのプログラムは、ソーシャル ネットワークに関するもので、ユーザーとそのプロファイルが存在することを意味します。プロファイル構造はUserProfile.

現在、考えられるさまざまなグラフの実装があり、最適なものを使用しているとは思いません。私はGraph構造を持っており、内部には type のリンクされたリストへのポインタがありますVertex。各Vertex要素には、値、次Vertexへのポインター、および type のリンクされたリストへのポインターがありますEdge。各Edge要素には、値 (重みと必要なものを定義できるようにするため)、次Edgeへのポインター、およびVertex所有者へのポインターがあります。

(CSV スタイルで) 処理してグラフに挿入するデータを含む 2 つのサンプル ファイルがあります。1 つ目はユーザー データ (1 行に 1 人のユーザー) です。2 つ目はユーザー関係 (グラフ用) です。最初のファイルはすぐにグラフに挿入されます。これは、私が常に先頭に挿入するためです。約 18000 人のユーザーがいます。2 番目のファイルは時間がかかりますが、それでも先頭にエッジを挿入します。このファイルには約 520000 行のユーザー関係が含まれており、グラフに挿入するのに 13 ～ 15 分かかります。簡単なテストを行ったところ、データの読み取りは非常に速く、瞬時に行われました。問題は挿入にあります。

この問題は、頂点のリンク リストを使用して実装されたグラフがあるために発生します。リレーションを挿入する必要があるたびに、それらをリンクできるように 2 つの頂点を検索する必要があります。これが問題です...〜520000のリレーションに対してこれを行うには、しばらく時間がかかります。

これをどのように解決すればよいですか？

解決策 1)グラフ (頂点部分) をリンク リストではなく配列として実装することを勧める人がいます。このようにして、すべての頂点に直接アクセスできるようになり、挿入が大幅に減少する可能性があります。しかし、配列に [18000] 個の要素を割り当てるという考えは好きではありません。これはどれくらい実用的ですか？私のサンプル データは ~18000 ですが、それよりも少ない場合や多い場合はどうすればよいですか? リンクされたリストのアプローチにはその柔軟性があり、メモリがある限り、好きなサイズにすることができます。しかし、配列はそうではありません。そのような状況をどのように処理しますか? あなたの提案は何ですか？

リンクされたリストの使用は、空間の複雑さには適していますが、時間の複雑さには適していません。また、配列の使用は時間の複雑さには適していますが、空間の複雑さには適していません。

このソリューションについて何か考えはありますか？

解決策 2)このプロジェクトでは、名前インデックスと ID インデックスに基づいてすばやく検索できる、ある種のデータ構造も必要です。このために、ハッシュ テーブルを使用することにしました。私のテーブルは、衝突解決として個別の連鎖を使用して実装されており、負荷係数が 0.70 に達すると、通常はテーブルを再作成します。次のテーブル サイズは、このLinkに基づいています。

現在、両方のハッシュ テーブルはUserProfile、ユーザー プロファイル自体を複製する代わりに、へのポインターを保持しています。それはばかげています。データを変更するには 3 つの変更が必要であり、そのようにするのは本当にばかげています。そのため、ポインターを に保存するだけUserProfileです。同じユーザー プロファイル ポインターも、各 Graph に値として保存されますVertex。

したがって、1 つのグラフと 2 つのハッシュ テーブルの 3 つのデータ構造があり、それらのすべてが同じ正確な を指していUserProfileます。グラフ構造は、最短パスなどを見つける目的に役立ちますが、ハッシュ テーブルは名前と ID によるクイック インデックスとして機能します。

グラフの問題を解決するために考えているのは、ハッシュ テーブルの値を に向けるのではなくUserProfile、対応する に向けることVertexです。それはまだポインターであり、使用されるスペースは多かれ少なかれありません。ポイントするものを変更するだけです。

このように、必要な各頂点を簡単かつ迅速に検索して、それらをリンクすることができます。これにより、~520000 のリレーションがすばやく挿入されます。

このソリューションを考えたのは、既にハッシュ テーブルがあり、それらが必要なためです。それなら、ユーザー プロファイルの代わりにグラフ頂点のインデックス作成にそれらを利用してみませんか? それは基本的に同じことです。私はまだUserProfile非常に迅速にアクセスできます.VertexUserProfile

しかし、最初のソリューションに対するこの 2 番目のソリューションの短所はありますか? それとも、最初のソリューションの長所と短所を圧倒する長所だけですか?

その他の解決策) 他に解決策があれば、私はすべて耳にします。しかし、前の 2 に対するそのソリューションの長所と短所を説明してください。私は今、これで無駄にしている時間があまりありません。このプロジェクトを進める必要があるので、そのようなことをしている場合変更する場合、何を変更する必要があるか、それが本当に正しいかどうかを正確に理解する必要があります。

これを読んで居眠りしてブラウザを閉じた人がいないことを願っています。しかし、私は本当にこれについて何をすべきかを決める必要があり、私は本当に変更を加える必要があります.

PS:私が提案した解決策に答えるときは、私と同じようにそれらを列挙してください。そうすれば、あなたが何を話しているのかが正確にわかり、自分自身をこれまで以上に混乱させないようにすることができます。

質問1：どのような状況下O(f(n)) = O(k f(n))で時間計算量分析の最も適切な形式でしょうか？

質問2：O表記法の数学的定義から作業してO(f(n)) = O(k f(n))、正の定数に対してそれをどのように示すkか？

最初の質問については、時間計算量の平均的なケースと最悪のケースの形式だと思います。私は正しいですか？そして、他に何を書くべきですか？

2番目の質問では、関数を数学的に定義する必要があると思います。k定数による乗算は、？の定義における任意の定数の値の再調整に対応するため、答えは次のようになりOますか？

The two programs below get n integers from file and calculates the sum of ath to bth integers q(number of question) times. I think the upper program has worse time complexity than the lower, but I'm having problems calculating the time complexity of these two algorithms.

Program 1:

Program 2:

The programs below gets n integers from 1 to m and sorts them. Again, I cannot calculate the time complexity.

Program:

It's ironic(or not) that I cannot calculate the time complexity of my own algorithms, but I have passions to learn, so please programming gurus, help me!