Logarithmic（Lcc）とUniform（Ucc）のコスト基準の違いと、それを計算に使用する方法を理解するのに問題があります。
誰かが2つの違いを説明し、おそらくA + B*Cのような問題の複雑さを計算する方法を教えてもらえますか
（はい、これは割り当ての一部です=））
助けてくれてありがとう！
/マーシン
3718 次
4 に答える
8
均一コスト基準は、関連するビット数に関係なく、すべてのマシン操作に一定のコストを割り当てますが、対数コスト基準は、関連するビット数に比例するすべてのマシン操作にコストを割り当てます
于 2012-02-01T16:58:25.713 に答える
3
問題サイズの影響の複雑さ 複雑さは問題のサイズに依存するため、複雑さを問題サイズの関数と定義します。 定義: サイズ n の問題に適用されるアルゴリズムの複雑さを T(n) とします。問題インスタンス (I) のサイズ (n) は、インスタンスを表すために使用される (バイナリ) ビットの数です。したがって、問題のサイズは、インスタンスのバイナリ記述の長さです。これは対数コスト基準と呼ばれます
ユニット コストの基準 次のことを前提とする場合: - すべてのコンピューター命令は 1 つの時間単位を使用し、 - すべてのレジスターは 1 つのストレージ ユニットであり、数値は常にレジスターに収まると仮定すると、入力の長さから問題のサイズとして入力の数を使用できます。 (ビット単位) は入力数の定数倍になります。
于 2011-11-08T16:21:07.120 に答える
2
均一コスト基準では、すべての命令に 1 単位の時間がかかり、すべてのレジスタに 1 単位のスペースが必要であると想定されています。
対数コスト基準は、すべての命令が (オペランドの長さに関して) 対数の時間単位を必要とし、すべてのレジスタが対数の単位のスペースを必要とすることを前提としています。
簡単に言うと、一様コスト基準では演算数がカウントされ、対数コスト基準ではビット演算数がカウントされます。
たとえば、8 ビットの加算器があるとします。
加算器の実行時間を分析するために均一なコスト基準を使用している場合、加算には単一の時間単位がかかると言います。すなわち、Ｔ（Ｎ）＝１である。
対数コスト基準を使用して加算器の実行時間を分析している場合、加算には lgn 時間単位がかかると言えます。つまり、T(N)=lgn です。ここで、n は、時間の複雑さに関して追加する必要がある最悪の場合の数値です (この例では、n は 256 になります)。従って、Ｔ（Ｎ）＝８である。
具体的には、256 を 32 に加算するとします。加算を実行するには、バイナリ ビットを 1 列、2 列、4 列など (ビット位置を意味する列) で加算する必要があります。数値 256 には 8 ビットが必要です。ここで、対数が分析に登場します。lg256=8。したがって、2 つの数値を加算するには、8 列で加算を実行する必要があります。対数コストの基準では、これら 8 つの加算計算のそれぞれに 1 単位の時間がかかると言われています。統一コスト基準では、8 つの加算計算のセット全体に 1 単位の時間がかかるとされています。
同様の分析は、空間に関しても行うことができます。レジスターは、一定量のスペース (均一コスト基準の下) または対数量のスペース (均一コスト基準の下) のいずれかを占有します。
于 2016-03-15T21:23:52.837 に答える
-2
I think you should do some research on Big O notation... http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions
If there is a part of the description you find difficult edit your question.
于 2010-05-21T16:17:43.140 に答える