私たちの教授とさまざまな資料は Summation(n) = (n) (n+1) /2 と言っており、したがって theta(n^2) です。しかし、直感的には、最初の n 項の和を求めるのに必要なループは 1 つだけです。だから、それは theta(n) でなければなりません。私はここで何が欠けているのだろうか?!
質問する
1600 次
4 に答える
2
これらの答えはすべて、元の質問と同じように問題を誤解しています。ポイントは、整数を合計するためのアルゴリズムiのランタイムの複雑さを測定することではなく、各パス中にステップを実行するアルゴリズムの複雑さについて推論する方法について話してiいる1..n. 挿入ソートを検討してください:i元のリストの 1 つのメンバーを挿入する各ステップで、出力リストはi要素が長いiため、挿入を実行するには (平均して) ステップが必要です。挿入ソートの複雑さは何ですか? これらすべてのステップの合計、またはifor iinの合計です1..n。その合計は がn(n+1)/2含まれているn^2ため、挿入ソートは O(n^2) です。
于 2013-09-14T01:34:41.980 に答える
1
問題は、合計式に時間の複雑さ theta(n^2) があると誤って想定していることだと思います。
数式には n^2 が含まれていますが、n^2 に比例する計算回数や時間は必要ありません。
あなたが言うように、ループ内の n までのすべてを合計すると、ループを n 回反復する必要があるため、theta(n) になります。
ただし、式 n(n+1)/2 の結果を計算すると、n の大きさに関係なく 1 回実行される単一の計算であるため、単に theta(1) になります。
于 2013-09-14T01:12:50.520 に答える