問題タブ [time-complexity]

私は現在、ローカルの sqlite データベースに格納されている大量の階層データにアクセスする必要がある iPhone のプロジェクトに取り組んでいます。より一般的な操作の 1 つは、ロールアップ ステータス フィールドの計算です。現在、そのアイテムのすべての子孫を再帰することでそれを行っています (深さは 1 ～ n レベルのどこでもかまいません)。ただし、これには多くのSQL呼び出しが必要になります。iPhone での各 sqlite 呼び出しは完了するまでに約 250 ミリ秒かかり、最終的には約 7.7 秒の処理時間になります。O(n) 時間未満でこのようなことを行う提案はありますか? 問題の根底にあるのは、膨大な数の SQL 呼び出しが行われていることだと思うので、それを減らしたいと考えています。

アルゴリズムの最悪の場合の複雑さを判断する方法を誰かに説明してもらえますか? 式 W(n) = max{t(I)|D の I 要素) を使用する必要があることはわかっています。ここで、D はサイズ n の入力のセットです。各要素に対して実行された操作の数を計算し、その最大値を取得しますか? これを達成するためのより簡単な方法は何ですか?

タイトルの通り、LinkedList クラスの size() メソッドの償却にかかる時間は O(1) 時間なのか O(n) 時間なのか気になります。

一定時間内にアイテムを検索できる dotnet のデータ構造が必要です。これは、データ構造が内部でインデックス作成を実装する必要があることを意味します。辞書は、この目的または他の目的に役立ちますか?

作成されたいくつかのアルゴリズムで最悪の実行時の複雑さの順序を取得しようとしています。しかし、アルゴリズムの基本操作の間違った量または間違った量を選択し続ける傾向があるという問題に遭遇しました。

私には、基本的な操作の選択は、科学というより芸術のように思えます。私のテキストボックスをグーグルで読んだ後、私はまだ良い定義を見つけていません. これまでは、比較や配列操作などの「アルゴリズム実行内で常に発生する操作」と定義してきました。

しかし、アルゴリズムには多くの場合、常に実行される多くの比較があるため、どの操作を選択しますか?

私はいくつかのデータ構造を調べていましたが、これが時間の複雑さであることに気付きました: O(log(log(n))))-competitive。

一定の競争力は、予想時間/最適時間の比率であると読みました。しかし、セット競争力を持つとはどういう意味ですか?

私はいくつかの基本的な画像フィルタリングアルゴリズムの複雑さを評価しようとしています。この理論を検証できるかどうか疑問に思いました。

Inverseのような基本的なピクセルごとのフィルターの場合、操作の数は入力のサイズ（ピクセル単位）に比例して増加します。

S=画像の辺の長さM=＃ピクセル入力とします

逆はO（M）またはO（S ^ 2）の次数です。

一方、畳み込みフィルターには、各フィルターの次のピクセル値を確立する際に畳み込む近傍のサイズを決定するパラメーターRがあります。

R=畳み込みフィルターの半径とします

畳み込みの次数はO（M *（（R + R * 2）^ 2）= O（M *（4R ^ 2）= O（MR ^ 2）

または、N =畳み込みフィルターのサイズ（近隣）をピクセル単位で指定する必要がありますか？

O（M *（N））= O（MN）

最終的に、畳み込みフィルターは、ピクセル数と近傍のピクセル数の積に線形依存します。

これが文書化されている論文へのリンクがあれば、それは大いにありがたいです。

敬具、

ギャビン

SO re Java ハッシュマップとそのO(1)検索時間に関する興味深い主張を見てきました。誰かがなぜそうなのか説明できますか? これらのハッシュマップが、私が購入したハッシュ アルゴリズムのいずれかと大きく異なる場合を除き、衝突を含むデータセットが常に存在する必要があります。

その場合、ルックアップはO(n)ではなくO(1).

誰かがO(1) であるかどうかを説明できますか?もしそうなら、どうやってこれを達成したのでしょうか?

Hashtable主な Java データ構造の概要と、それぞれの時間の複雑さ (追加、検索、削除などの特定の操作について)を含む Web サイトLinkedListの参照を誰か教えてもらえますか? O(n) です。メモリ使用量などの詳細もいいでしょう。

これは、アルゴリズムのデータ構造を考えるのに非常に役立ちます。

重複の可能性:
O(1/n) アルゴリズムはありますか?

あなたのコードが O(1) 未満の Big O になる可能性はありますか?