2つの行列を乗算する場合、結果を格納するために3番目の行列を割り当てる必要があります。アルゴリズムのメモリ消費量を計算するときに、この割り当てを考慮する必要がありますか？
2 に答える
1
アルゴリズムに必要なスペースが、結果を格納するために必要なスペースよりも少ないという議論を想像することはできません。これは、必要なスペースの下限である必要があります。
しかし、どうやら私の想像力は目前の仕事に任されておらず、入力パラメーター用のスペースも出力/結果用のスペースもアルゴリズムに対してカウントされるべきではありません。
だから（以下のコメントが私を納得させたように）：いいえ。
于 2012-01-14T02:41:25.307 に答える
0
他の応答が言うように、行列自体が占めるスペースと乗算アルゴリズムを区別する必要があります。
従来のNxM行列データ構造の場合、使用されるスペースはO（NM）です。
アルゴリズム自体に関しては、次のように異なります。基本的な順次乗算アルゴリズムは、一度に1つの要素を乗算および合計するため、O（1）スペースを使用します。
NxMおよびMxP行列を乗算する並列アルゴリズムでは、各プロセスが1つの乗算値を計算するため、各プロセッサはO（1）スペースを取る必要がありますが、スペースではO（X）です。ここで、Xはソリューションで動作する並列プロセスの数です。
于 2012-01-14T03:31:24.653 に答える