2

ニュートン法を使用してユーザー定義の数値の平方根を計算するJavaプログラムを作成しました。アルゴの主な操作は次のようになります。

answer = guess - ((guess * guess - inputNumber) / (2 * guess)); 
while (Math.abs(answer * answer - inputNumber) > leniency) {
    guess = answer;
    answer = guess - ((guess * guess - inputNumber) / (2 * guess));
}

私は今、アルゴリズムの複雑さ（宿題です）を見つけようとしています。ここから、ニュートン法の時間計算量はO（log（n）* F（x））であることを読みました。

ただし、上記のコードスニペットから、時間計算量は次のように解釈されました。

O(1+ ∑(1 to n) (1) ) = O(1+n) = O(n)

ここで何が間違っているのかわかりませんが、wikiの説明を読んだ後でも、大きなOSの格差を理解できないようです。

また、「アルゴリズムの複雑さ」は「時間の複雑さ」と同義であると思います。そうするのは正しいですか？

私は初心者の学生であり、バックグラウンドに値するいくつかの「タッチアンドゴー」プログラミングモジュールを持っているので、このパラドックスを説明するのに助けていただければ幸いです。

前もって感謝します ：）

4

1 に答える 1

1

問題は、あなたが実際nにあなたの計算について何も知らないということです-あなたはそれがどうあるべきかを言いません。アルゴリズムの次の反復の実際のエラーを計算すると（実行してください！）、たとえば次のように表示されます。がa1以上で、エラーが1未満の場合、基本的に、反復ごとに有効な場所の数が2倍になります。したがって、p小数点以下の桁数を取得するには、log(p)反復を実行する必要があります。

于 2012-11-04T18:44:27.580 に答える