procedure max (a[1..n]: integers)
max := a[1]
for i := 2 to n
if max < a[i] then max := a[i]
複雑さですか、O(1)それともO(n)最良のシナリオですか? シーケンスにはn要素が含まれています。擬似コードです。
質問する
410 次
7 に答える
8
このアルゴリズムでは、最良の場合と最悪の場合の漸近的な実行時間に違いはありません。いずれの場合も、配列全体 (n要素) をトラバースする必要があり、アルゴリズムは O(n) になります。
理論的には、任意の配列の最大要素を O(n) 未満で見つける方法はありません。これは、常に各要素に少なくとも 1 回アクセスする必要があるためです。
于 2009-11-11T07:06:16.450 に答える
4
アルゴリズムはO(n)、最良の場合、平均的な場合、および最悪の場合です。また、使用すべき場所を参照して使用するだけなので、機能しません。a1 <>
于 2009-11-11T07:07:22.120 に答える
2
O(n) - n 個の要素、または n 倍 (n/2、n/4 など) をスキャンする必要がありますが、それでも O(n) です。
于 2009-11-11T07:05:32.753 に答える
2
大まかに言えば、O(1) は、入力のサイズに関係なく、固定数のステップでソリューションを実装できることを意味します。
O(n) は、n 個の入力がある場合、解が An ステップで実装されることを意味します (A は数値であり、別の変数ではありません)。明らかに、2 から n までカウントする for ループがある場合、つまり n サイクルです。つまり、入力要素が An の場合、ループは 2 から An までカウントします。つまり、入力と同じレベルにあることを意味します。 O(n)です。しかし、それがリニアスキャンのやり方です。:)
于 2009-11-11T07:17:15.663 に答える
0
配列全体をトラバースする必要があります。したがって、複雑さは O(n) になります。
于 2009-11-11T07:29:00.740 に答える
0
次のようなコードがある場合:
for i := 2 to n
その場合、そのコードは O(n) ベストケースになります。
なぜ一定時間だと思うのですか？
于 2009-11-11T07:11:44.147 に答える
-1
の上）
配列がソートされていれば O(1) を達成できるので、最後の要素を返すだけです。
しかし、ランダムに配置された要素では、この問題の最適な順序は O(n) です
于 2009-11-11T07:32:22.793 に答える