1

単純なアルゴリズムの時間と空間の複雑さを使用するかどうかを決定するように求められます。問題は、数字がどこから来ているのか完全には理解していないということです。例から、加算、減算、除算、乗算をプリミティブ演算としてカウントすることが提供されました。

ここでは、提供された式を使用して標準偏差を計算するアルゴリズムの擬似コードを投稿しています。

2 *（n-1）の加算記号、1つの除算記号、2つの乗算記号、1つの減算記号が表示されます。

時間計算量のためにここで他に何を数えなければなりませんか？そして、スペースの複雑さをどうするか？

// X is passed array, and N is number of elements in array.
Algorithm calculateStandardDeviation(X, N)
{
    private double arraySum;
    private double arrayMean;
    private double xi2;
    private double standardDeviation;

    foreach (arrayValue in X)
    {
        arraySum = arraySum + arrayValue;
    }

    arrayMean = sum / N;

    foreach (arrayValue in X)
    {
        xi2 = xi2 + Math.Pow(arrayValue, 2);
    }

    standardDeviation = Math. Sqrt(((1/N) * () * xi2) - Math.Pow(arrayMean, 2));

    return standardDeviation;
}
4

1 に答える 1

3

アルゴリズムの複雑さは、皮肉なことに、必要に応じて一般的または複雑にすることができます。コンピュータサイエンスの標準であるように、O（...）表記の複雑さに取り組んでいる場合は、@davidrobinsonが現在の状況に関して正しいです。

forループは通常、N時間計算量の次元を追加します。ここで、Nはループに含まれる実行の数です。他のすべてのことは、O（1）の「一定の」時間で実行されます（別のO（1）時間opと同じ量の物理時間がかかることを意味するわけではありません）。したがって、時間計算量は、すべての操作の線形加算またはO（N + N + 1 + 1 + ...）= O（2N）です。これは、クラスで学んだと思いますが、O（N）になります。時間の複雑さ。

スペースの複雑さについても同じです。入力サイズが大きくなるにつれて何かが大きくなりますか？それはイエスです-配列に要素を追加すると、配列は大きくなります。したがって、それもO（N）として成長します。あなたには他の一定のスペース要因がありますが、私たちはそれを大きなものとして落としています-ああ、あなたに

線形-O（N）-時間と空間の複雑さ。

于 2012-09-18T19:20:48.350 に答える