2

配列は次のように宣言されていますか：
int array[M]、O(1)スペース内またはO(n)？ここで、Mは固定値です。O(n)それは単一の変数ではなく、配列全体であるため、私には理にかなっています。O(1)でも、サイズが決まっていて変わらないから かもしれないと思います！

4

3 に答える 3

6

配列が固定サイズであり、入力のサイズによって変化しない場合は、定数として=O(1)として表すことができるため、配列は変化しません。例として、100万（またはその他の任意の数）の整数を実行するアルゴリズムで状態を保持するためにサイズ5の配列が必要な場合があります。重要なことは、独立していることです。c * O(1)O(1)cMN

ただしM、入力のサイズまたは入力サイズに直接依存する値（N/2または他の線形関数）を表す場合は、実際には、入力サイズMとともにN大きくなるため、になりますO(N)。例としては、アルゴリズムを実行する（つまり、二乗の合計を決定する）すべての入力数値を保持する配列があります。

于 2011-05-03T16:26:04.853 に答える
1

Mが定数の場合、O（1）と言います。O（n）の場合、そのサイズはMの線形関数である必要がありますが、この場合はそうではありません。

于 2011-05-03T16:27:35.393 に答える
0

あなたが与えられた他の答えは正しいです、正式にはそれはO（1）です。

ただし、「定数」の意味については慎重に検討してください。O（...）表記は、実際のコンピュータープログラムのパフォーマンスを測定するためのものではなく、アルゴリズムを複雑さによって分類するためのものです。

オブジェクトの配列でそれぞれを1回だけ読み取るアルゴリズムを実装している場合（たとえば）、「OK、要素の数をNに固定しましょう」と言うことができますが、それではアルゴリズムはO（1）複雑度クラス、アルゴリズムは引き続きO（n）ですが、テストケースをn = Nに制限しています。ここで、Nは固定されています。

于 2011-05-03T16:33:39.937 に答える