複雑性分析では、なぜ++は2つの操作と見なされますか？

StackOverflow https://stackoverflow.com/questions/443423

質問

私のコンピュータサイエンスIIクラスでは、教授は++、-、* =などを2つの操作と見なしています。ただし、アセンブリレベルでは、これは実際には2つの操作ではありません。誰かが説明することができますか、これは単純にするためですか？

役に立ちましたか？

解決

実際には、読み取り、インクリメント（またはその他）、書き込みの3つの操作であると考えています。これは、ある種の共有メモリからある種のローカルストレージ（レジスタやスタックなど）に読み取り、ローカルストレージで動作してから書き戻すことを前提としています。

アセンブリレベルでの操作の数は、増分するもの、プラットフォーム、ハードウェアなどによって異なります。

他のヒント

++（例：b ++）は簡略化されているため

b = b + 1

そこには2つの操作があります。加算（b + 1）と、加算の値の元の変数への割り当てです。

複雑さの分析を行うときに面倒なのはなぜですか？それはただのO（1）です：-）

編集：投票したときに理由を教えてください。質問には complexity というタグが付けられているため、実際の定数ではなく、大きなOの概念が最も重要だと思います。また、他の回答で既に述べたように、これがいくつの操作であるかは、多くの要因に依存します：操作、プラットフォーム、コンパイラなどのカウント方法

いくつかの推測を投げます。

  • あなたの教授は通訳言語に言及していますか？
  • ++ iはi ++とは異なるのでしょうか？

  • 選択するアセンブリ言語に中間ストレージ変数が必要な場合がありますか？

    add reg_temp, reg_i, 1
mov reg_i, reg_temp

追加とセッターではありませんか？

i + = 1に似ていますか

教授は、おそらく値を取得し、その値に1を加算してから変数に代入する必要があることを参照しているだけです。

アセンブリレベルでは、すべてがレジスタで実行されるため、Aに変数があります

ADD AX,1

ただし、コンパイルされた言語ではすべてを保存する必要があるため、i ++は（擬似アセンブリで）

MOV AX,i
ADD AX, 1
MOV i, AX

3つの操作です...基本的なアーキテクチャを完全に忘れていない限り...

あなたはちょっと、「ジュリーは出ていない」を思い出した。ずっと前に聞いた問題。

  

＆quot;プリインクリメントはポストインクリメントよりも高速です＆quot;

Googleで簡単に検索しました。

  1. まだ多くの人がそれを真実だと思っています。
  2. 他の人は、コンパイラが非常に最適化されており、比較の高レベルのコードはベンチマークできないと主張しています。
  3. まだ他の人々は違いはないと主張します。

コンテキストに応じて2つの意味があるため、私の意見では2以上である必要があります。また、見たときにそれらを思い出す必要があります。

a = b ++ は a = bと同じです。 b = b + 1

and

a = ++ b は b = b + 1と同じです。 a = b

これは、ほとんどの初年生を崖から追い出すのに十分な混乱です。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top