動的配列の償却分析で間違った総コストを計算するために、宿題にポイントをドッキングしました。採点者はおそらく合計のみを見て、私が行った手順は見ていないと思います.mallocを説明したと思いますが、回答キーは考慮していませんでした.
ここに私の分析のセクションがあります：
表示された例では malloc が説明されていませんでしたが、ビデオを見て非常に理にかなっていたので、そこに入れました。malloc は比較的コストのかかる操作ですが、ここではおそらく O(1) になるので、省略できたはずです。
しかし、私の質問は次のとおりです。この種の分析を行う場合、コストを計算する方法は 1 つしかありませんか? 客観的な善悪のコストはありますか、それとも本当に重要なことは結論です。
「この種の分析を行う場合、コストを計算する方法は 1 つしかありませんか?」と質問されました。答えはノーだ。
これらの分析は、実際のモデルではなく、マシンの数学的モデルに基づいています。「サイズ変更可能な配列への追加は O(1) 償却される」などと言うとき、アルゴリズムで必要なさまざまな手順のコストを抽象化しています。動機は、あなたと私が異なるマシンを所有している場合でも、アルゴリズムを比較できるようにすることです。
ただし、さまざまな物理マシンに加えて、さまざまなモデルのマシンもあります。たとえば、一部のモデルでは整数を定数時間で乗算できません。一部のモデルでは、変数を無限精度の実数にすることができます。一部のモデルでは、すべての計算が無料で、追跡される唯一のコストは、メモリからデータを取得する際のレイテンシです。
ハードウェアが進化するにつれて、コンピューター科学者は、アルゴリズムの分析に使用される新しいモデルについて議論します。たとえば、Tomasz Jurkiewiczの「The Cost of Address Translation」などの作品を参照してください。
モデルには、malloc の具体的なコストが含まれているようです。それは間違いでも正しくもありません。お使いのコンピューターではより正確なモデルである可能性があり、グレーダーではより正確でないモデルである可能性があります。