アルゴリズムの複雑さには主に何が含まれますか?

アルゴリズムの複雑さ:

時間計算量

コンピューター サイエンスでは、時間計算量は、時間計算量度とも呼ばれます。アルゴリズムの時間計算量は、アルゴリズムの実行時間を定性的に記述する関数です。これは、アルゴリズムへの入力値を表す文字列の長さの関数です。時間計算量は、多くの場合、この関数の下位項と主要な係数を除いて、ビッグ O 表記法で表現されます。このアプローチを使用する場合、時間計算量は漸近的である、つまり入力値のサイズが無限大に近づくと言えます。

時間計算量を計算するには、通常、アルゴリズムの演算ユニットの数を推定しますが、各ユニットの実行時間は同じです。したがって、アルゴリズムの合計実行時間と演算単位の数は、最大でも一定の係数だけ異なります。

同じサイズの入力値が異なると、アルゴリズムの実行時間が異なる可能性があるため、通常はアルゴリズムの最悪の場合の複雑度を使用し、T(n) として表されます。これは次のように定義されます。任意のサイズの入力 n に必要な時間 最大実行時間。あまり一般的ではないもう 1 つの方法は平均ケース複雑度です。これは通常、指定された場合にのみ使用されます。時間計算量は、関数 T(n) の自然な特性によって分類できます。たとえば、T(n) =O(n) のアルゴリズムは「線形時間アルゴリズム」と呼ばれますが、T(n) =O(M ^n) かつ M= O(T(n)) であり、M≥n>1 のアルゴリズムは「指数関数的時間アルゴリズム」と呼ばれます。

アルゴリズムにかかる時間は、アルゴリズム内のステートメントの実行数に比例し、ステートメントが多いアルゴリズムが実行されると、より多くの時間がかかります。アルゴリズムにおけるステートメントの実行数は、ステートメント頻度または時間頻度と呼ばれます。それをT(n)と表します。
一般に、アルゴリズムにおける基本演算の繰り返し実行回数は、T(n) で表される問題サイズ n の関数です。補助関数 f(n) がある場合、n が無限大に近づくと、 T(n)/f(n) の限界値がゼロに等しくない定数である場合、f(n) は T(n) と同じオーダーの大きさの関数であると言われます。 T(n)=O(f(n)) と表され、O(f(n)) はアルゴリズムの漸近時間計算量、または略して時間計算量と呼ばれます。
さまざまなアルゴリズムの中で、アルゴリズム内のステートメントの実行数が一定の場合、時間計算量は O(1) ですが、時間頻度が異なる場合、時間計算量は T のように同じになる場合があります。 ( n)=n2 3n 4 と T(n)=4n2 2n 1 は周波数が異なりますが、時間計算量は同じで、どちらも O(n2) です。

時間頻度

アルゴリズムの実行にかかる時間は理論的に計算できません。それを知るには、コンピューター上でテストを実行する必要があります。しかし、コンピューター上ですべてのアルゴリズムをテストすることは不可能であり、その必要はなく、どのアルゴリズムに時間がかかり、どのアルゴリズムに時間がかからないかだけを知る必要があります。また、アルゴリズムにかかる時間は、アルゴリズム内のステートメントの実行数に比例し、ステートメントが多いアルゴリズムが実行されると、より多くの時間がかかります。アルゴリズムにおけるステートメントの実行数は、ステートメント頻度または時間頻度と呼ばれます。それをT(n)と表します。

空間複雑度

時間計算量と同様に、空間複雑度は、コンピューター内でアルゴリズムが実行されるときに必要な記憶域の測定値を指します。次のように記録されます:

S(n)=O(f(n))

アルゴリズムの実行中に必要なストレージ スペースには 3 つの部分が含まれます:

• アルゴリズム プログラムによって占有されるスペース;

• 初期データ入力によって占有されるストレージ スペース;

• アルゴリズムの実行中に必要な追加空間。

多くの実際的な問題では、アルゴリズムが占有するストレージ容量を削減するために、通常、圧縮ストレージテクノロジが使用されます。

以上がアルゴリズムの複雑さには主に何が含まれますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。