RAMマシンモデルの規約

計算モデルを明示的に知らずにアルゴリズム漸近ランタイムが与えられるとき、使用される正確なモデルのための慣習は何ですか?

私の理解では、ほとんどの問題は単価RAMを使用していますが、整数乗算などの一部はログコストRAMを使用しますが、一部の場合は作成者によって異なります。

ユニットコストは、一般的に使用されるアルゴリズム(したがってその人気度)にマッピングする方が簡単ですが、ログコストRAMは計算の真の尺度としてより正確に見えます。

ログ・コストRAMの場合、標準の最大線形時間の等価性があるように見えます。

For unit-cost RAM, there are different possibilities (in order
of decreasing model power):
a. (naive) unlimited word size with multiplication
b. unlimited word size (with addition but not
multiplication)
c. log-limited word size (with different conventions)
d. pointer machines (also called storage modification
machines; this is a natural model but appears more restrictive than
unit-cost RAM).

大会は(c)と考えていますが、ここでもさまざまな選択肢があります。 $ s $、$ s≦t $を持つ$
mathrm {TimeSpace}(t、s 、 mathrm {cells})$の賢明な選択は、セル$ 0.O(s) $
mathrm {Time}(O(t))= mathrm {TimeSpace}(O(t)、O(t)、 mathrm
{cells })$($ t $が入力の長さを超えていると仮定すると、$ t ^ {O(1)} $
cellsを使って同等のモデルが得られるかどうかわかりません)。しかし、これが標準であるかどうか、他の微妙な違いがあるのか​​、多項式空間以上を使うアルゴリズムでは単位コストRAMが定義されていないのか分かりません。

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です