logN + 1のメモリ要件を持つアルゴリズムがあるとします。ここで、Nは問題のサイズ（処理するビット数）です。このメモリ要件を（logN）/ 2+1に減らす2番目のバージョンを提案します。Big-O分析では定数が無視されることを学びました。そのため、両方のアルゴリズムバージョンの複雑さはO（logN）です。
ここで、アルゴリズムの2番目のバージョンを使用して節約したメモリを計算すると、次のようになります。
N = M（N）= 1で保存されたメモリ-[（logN）/ 2 + 1] / [logN + 1] limN
→∞M（N）= 1/2
これは、漸近的にメモリの50％を常に節約することを示しています。Big-O分析でこのゲインを確認できない理由がわかりません。
私の2番目の質問は、Big-O表記についての私の理解が間違っている場合、アルゴリズムの2番目のバージョンで保存されたメモリを強調表示する適切な方法は何ですか？
big-O表記には定数要素が含まれていないことに注意してください。関数f（n）= nおよびg（n）= 10 100 nは両方ともO（n）ですが、f（n）はg（n）よりもはるかに小さい関数です。
分析は正しいです。スペース使用量（log n）/ 2 -1を作成できる場合は、（制限内で）必要なメモリ量が半分になります。ただし、big-Oは定数係数を無視するため、これはbig-O分析には表示されません。他のいくつかの回答で述べたように、big-O表記は長期的な成長率をキャプチャします。定数は使用されるスペースの絶対量について詳しく教えてくれるかもしれませんが、定数はスペース使用量の長期的な成長率を制御しません。
より正確な分析を行いたい場合は、前後の正確なメモリ使用量を示してから、メモリ使用量を50％削減したと言うことができます。アルゴリズムとデータ構造に関する多くの論文には、実際には一定の要因が含まれており、一定のスピードアップが得られていると述べています。たとえば、コレスキー分解アルゴリズムとガウスの消去法はどちらも線形システムを解くためのO（n 3）アルゴリズムを提供しますが、コレスキー分解を使用できる場合は、操作が約50％少なくなります。これらのトピックを扱っているほとんどの教科書は、両方のアルゴリズムがO（n 3）であるが、それを使用できる場合は前者が後者よりも好ましいと述べています。
お役に立てれば！
Big-Oは一定の要因を考慮していません。これは、アルゴリズムがどのようにスケーリングするかの尺度にすぎません。したがって、log Nに比例して大きくなるものはすべてO（log N）です。これは相対的な尺度であり、1人の給与が10,000から12,000になり、もう1人の給与が1,000,000から1,200,000になったにもかかわらず、2人の給与が10％上昇したと言っています。毎年10％の上昇があると言われた場合、誰かの総支払い額を知ることは期待できないので、アルゴリズムがO（log N）増加することがわかっている場合は、アルゴリズムの総コストを知ることを期待しないでください。 。
アルゴリズムの2番目のバージョンがメモリの半分を使用しているが、スケーリング動作が同じである場合は、単にメモリの半分を使用していると言います。
Big-Oは、アルゴリズムまたは実装がどのように拡張されるかを決定するのに非常に役立ちます。定数の改善（この例では半分）は依然として有用ですが、問題のサイズが1桁大きくなると、ほとんど効果がありません。