変数の初期化/代入文は単一の操作以上ですか？

Question

私はちょうどアルゴリズムの性能分析について学んでいます

私の質問：int i=0;は2つの操作としてカウントされます：assisgment、intialization。 私は、パフォーマンスを記述する方法の例として操作の数を使用する漸近分析を使用しています

Answer 1

これに対する正解はありません。

一部のコンテキストでは、1つの算術演算を「1」演算として解析する場合があります。他の時間に、彼らは操作が何サイクルかかるか正確に気にするかもしれません。 intを追加することは浮動小数点数を掛けるよりも安いです。

多くの文脈で、プログラマは、ポインタの逆参照はO(1)であると言います。しかし、実際にnが無限に行く場合を考慮している場合は、nが宇宙のサイズに似ている場合は、ポインタを参照解除することはO(1)操作であると言っても意味がありますか？ In some theoretical contextsの場合、ポインタの逆参照は本質的にO(log n)と言われます。

O(log n)でも、物理的に現実的ではない可能性があると言いましたが、私は物理学者と話しました。彼は、与えられたボリューム空間で宇宙が持つことができる最大の情報密度があると言います。これは「Bekenstein Bound」と呼ばれ、最大エントロピーはブラックホールによって達成されます。あなたが空間の容積がnであると仮定すれば、O(n)ビットのメモリしか持てないということは、基本的には銀河サイズのコンピュータでは、ビットがsphere packing problemのボールのように詰め込まれなければならないことを意味し、ビットはO(n^{1/3})として増加しています。情報が光の速度より速く進まないので...ポインターの逆参照には漸近的にO(n^{1/3})が必要ですか？ O.o

ポイントは、これを超えることはありません。あなたが漸近分析で行うことは、最終的に近似であり、どれくらいの時間がかかるかについての有用なアイデアを得ようとしているだけです。あなたが大事なことに集中するために、あなたが確信していることは事実上問題ではないでしょう。O(1)として分析することができます。別の状況では、同じことを、彼らが仕事の「最も」を表しているなら、異なって分析したいと思うかもしれません。

はIMOあなたが就職の面接ではこのようなものについての質問に答える方法を知りたい場合は、複数の異なる方法でそれを分析し、あなたが「のようなものが一つの操作としてint i = 0;のカウントを行うことを理解することがそれらを表示するために準備する必要があります基本的に大会です。