問題タブ [complexity-theory]

C ソースの循環的複雑度を測定するために使用できるツールを知りたいです。

同じ質問をしている他の投稿を見たことがありますが、C ソース専用の特定のツールを知りたいです。

LINQ to [お気に入りのプロバイダーをここに挿入] についてというよりも、この質問はメモリ内コレクションの検索またはフィルター処理に関するものです。

IEnumerableorを実装するオブジェクトでLINQ（または拡張メソッドの検索/フィルタリング）が機能することを知っていますIEnumerable<T>。問題は、列挙の性質上、すべてのクエリの複雑さは少なくともO(n)ですか?

例えば：

この場合、すべてのアルゴリズムは少なくともO(n)を要します。ただし、私の理解が正しければ、このクエリは列挙によって解決されるため、以前に注文した場合でもO(n)を取る必要があります。list'something'list

• O(log(n))でクエリを解決するためにできることはありますか?
• パフォーマンスが必要な場合、Array.Sort と Array.BinarySearch を使用する必要がありますか?

アルゴリズムの時間の複雑さについて話すとき、「一定の償却時間」とはどういう意味ですか?

リストへの変更のリストがあります-追加と削除。リストは非常に大きくなる可能性があります。たとえば、10,000 アイテムです。

変更後のリストの状態を知りたい 9'000.

リストを最初から9'000に変更するまで歩くことができました。それは私には少し長すぎるようです。

アイテムのリストを保持し、アイテムが追加されたときと削除されたときに記録し、このリストをたどって、特定の変更でリストに何があるかを確認できます。Adds と Deletes の可能性が同じである場合、実行する必要があるリスト要素の数は半分になります...

しかし、Big O 表記法では、問題のサイズを半分にしても効率が良くなることはありません (私の理解が正しければ)。

100 回目または 1000 回目の変更ごとにリストの状態をキャッシュすることもできますが、繰り返しになりますが、アイテムの数を 'n' で割っても効率が良くならないということです。

では、これを行う効率的な方法は何ですか？これを行う効率的な方法はありますか？

詳細: 具体的には、カスタム アロケーターでのメモリ割り当て/割り当て解除を追跡しています。各割り当て/解放は、リスト内のイベントです。各割り当てには一意の ID があります。(例) 9'000 イベントの後に現在割り当てられているものを知りたいです。

私の最初のアイデアは、IDごとに、割り当てられたイベントと割り当て解除されたイベントを保存することでした。次に、割り当てイベントが 9000 より大きい最初の割り当てまで、このリストをたどります。

私はマイク F が指摘した点が好きです - 最も近い 100 番目のアイテムから歩くのは一定の時間です...

私は最近、再帰と Big-O 記法を含むコンピューター サイエンスの宿題に取り組んでいます。私はこれをかなりよく理解していると思います (ただし、完全ではないことは確かです!)。奇妙なことに、それを見ると、宿題の中で最も単純なもののように見えます。

次の再発の解決策として、big-Oh 表記法を使用して最高の成長率を提供してください。

T(1) = 2

T(n) = 2T(n - 1) + 1 for n>1

選択肢は次のとおりです。

• O(n log n)
• O(n^2)
• O(2^n)
• O(n^n)

大きな O が上限として機能し、プログラムまたはプロセスにかかる最大の計算量または最大実行時間を表すことを理解しています。この特定の再帰は O(n) であるべきだと思います。なぜなら、再帰は n の値ごとに 1 回しか発生しないからです。n が利用できないので、他の 3 つのオプションである O(nlogn) よりも良いか、悪いかのどちらかです。

だから、私の質問は: なぜこれは O(n) ではないのですか?

私は現在、Big-O と実行時間を扱う課題に取り組んでいます。非常に簡単に思える質問が 1 つありますが、正しく行っているかどうかはわかりません。残りの問題はかなり難しく、ここで何かを見落としているような気がします。

まず、次のようなものがあります。 アルゴリズム A の実行時間は 50n^3 です。コンピューター A。1 操作あたりの速度は 1 ミリ秒です。1 回の操作で 2 ミリ秒の速度を持つコンピューター B。サイズ 300 のインスタンス。

アルゴリズム A がコンピューター A でこのインスタンスを解決するのにかかる時間と、コンピューター B でかかる時間を調べたいと考えています。

私がやりたいのは、n に対してサブ 300 であるため、50*(300^2) = 4500000 になります。

次に、最初のコンピューターの場合は 1 を掛け、2 番目のコンピューターの場合は 2 を掛けます。

これは私には奇妙に感じますが、「実行時間」が 50n^3 であり、「演算回数が 50n^3」ではないため、時間を掛けているような気がします。ミリ秒の二乗の単位になってしまいますが、これはまったく正しくないようです。

私が正しいかどうか、そうでない場合は、質問が実際に何を意味するかを知りたいです。

In programming we face various situations where we are required to make use of intermediate STL containers as the following example depicts:

Or

Which approach is better in terms of time and space complexity considering the present state of C++ compliers?

次の場合の STL マルチセット、マップ、およびハッシュ マップ クラスの Big O 表記の複雑さを知りたいです。

• エントリの挿入
• エントリへのアクセス
• エントリの取得
• エントリの比較

std::list::size()最近、線形の複雑性があると言及している人がいることに気付きました。一部の情報源
に よると、これは実際には実装に依存しているため、標準では複雑さがどうあるべきかが規定されていません。このブログエントリ のコメントには次のように書かれています。

実際には、使用している STL によって異なります。Microsoft Visual Studio V6 は size() を {return (_Size); として実装します。} 一方、gcc (少なくともバージョン 3.3.2 および 4.1.0 では) は { return std::distance(begin(), end()); のように行います。最初の速度は一定で、2 番目の速度は o(N) です。

1. したがって、私の推測では、VC++ クラウドsize()は常に複雑であり、Dinkumware はおそらく VC6 以降その事実を変えていないでしょう。私はそこにいますか？
   
2. 現在はどのように見えますgccか? それが本当に O(n) である場合、なぜ開発者はそうすることにしたのですか?

アプリケーション内でどれだけの人がログに記録しているのか?

私はこれを見ました：

「私は通常、アプリケーションによってキャッチされた例外をログに記録するために ERROR ログ レベルを使用するのが好きです。メソッドを開始または終了するたびに表示する「第 1 レベル」のデバッグ スキームとして INFO ログ レベルを使用します。そこから使用します。詳細情報を追跡するための DEBUG ログ レベル。FATAL ログ レベルは、Web ベースのアプリケーションでキャッチできなかったすべての例外に使用されます。」

このコードサンプルが含まれていました：

しかし、これは方法に多くを追加しているようです。たとえば、通常はおそらく 7 行のコードであるクラスが、突然 12 行のコードになります。この方法はまた、その明快さと単純さの一部を失います。

しかし、ロギングを適切に行うことの利点は良いと言えます。たとえば、実稼働システムでのパフォーマンス監視、実稼働での異常なバグの追跡 (このすべてのログを常にオンにしているわけではありません。

したがって、私は人々が何をしているのか疑問に思っています。乾杯アンソニー