私は数値解析を勉強していますが、アルゴリズムには「約 n^2/2」の複雑さがあると読むことができます。
複雑さが書き込み/読み取り/乗算/合計操作に関係していることは知っていますが、「正確に」ではなく「約」である理由がわかりません。
1 に答える
1
アルゴリズム分析では、支配的な成長項を介してアルゴリズムの成長率のみを記述するのが一般的です。たとえば、アルゴリズムの実際の実行時間がn 2/2 + 13n + 1の場合、nが大きくなると（たとえば、n> 50）、実行時間のほとんどすべてがn2/2項で説明されます。他の2つの用語による寄与はほとんどありません。
コンピュータサイエンスの多くでは、アルゴリズムはbig-O表記法を使用して記述されます。これは、支配的な成長項を除くすべてを完全に破棄し、それでもすべての定数要素を破棄します。数値計算では、通常、支配的な成長項とその一定の係数を維持するだけです。これは、入力が大きい場合、その項が実行時間のほとんどすべてを決定するためです。ただし、定数係数は、さまざまなアルゴリズムを比較するのに役立ちます。
つまり、正確な分析を行うことはできますが、問題のサイズが大きい場合にはあまり役立ちません。支配的な成長期間は本当に重要なすべてです。
お役に立てれば！
于 2013-02-03T22:08:14.877 に答える