1. 概要

どんな問題でも、複数の解決策があります。 ただし、研究者の目標は、実行にかかる時間が短く、メモリの消費量が少ないソリューションを見つけることです。

コンピュータサイエンスでは、ソリューションはプログラムに変換されます。 したがって、最適なソリューションの選択は、実行する必要のあるリソースの数によって異なります。 コンピュータ上のリソースは、使用するメモリスペースの量と実行時間です。 両方とも最小限にする必要があります。

時間と空間の複雑さは、最適なアルゴリズムの2つの重要な指標です。

このチュートリアルでは、時間と空間の複雑さを定義します。さまざまなタイプの時間と空間の複雑さについて説明し、それぞれの例を示します。

最後に、これらのコアの違いを強調して、このチュートリアルを終了します。

2. 時間計算量とは何ですか？

時間計算量は、アルゴリズムの実行に必要な時間を表す計算量です。時間計算量は、アルゴリズムのすべてのステートメントにかかる時間を測定します。 したがって、処理されるデータのサイズに大きく依存します。 さらに、アルゴリズムの有効性を定義し、そのパフォーマンスを評価するのに役立ちます。

時間計算量は入力データのサイズから計算される漸近関数であるため、Landauの数学記号：、、、およびを表記として使用します。 ここで、各シンボルは異なる時間計算量を定義します。

表記は、必要な時間の上界を表し、最悪のシナリオを説明します。 表記は、必要な時間の下限を示します。 最良のシナリオについて説明します。 表記は、上限と下限に必要な時間をフレーム化します。 それは平均的なケースのシナリオを語ります。

各アルゴリズムが実行の最後に到達するまでに費やした時間に応じて、さまざまなタイプの時間計算量があります。 したがって、時間計算量のタイプは、プログラム内の命令またはステートメントによって異なります。 いくつかの例は次のとおりです。一定時間（）、線形時間（）、対数時間（）など。

3. 時間計算量を計算する方法

時間計算量を計算するには、プログラムの各行を考慮する必要があります。 したがって、 階乗関数の例を取り上げています。 階乗関数の時間計算量を計算してみましょう。

1. fact ← 1 
2. i ← 2 
3. while i ≤ n do 
4.     fact ← fact ∗ i 
5.     i ← i + 1 
6. end while

このアルゴリズムの時間計算量の関数とします。 1行目と2行目の時間計算量は。 行番号3はループを示します。 したがって、4行目と5行目を繰り返す必要があります。 したがって、4行目と5行目の時間計算量はになります。

最後に、すべての行の時間計算量を追加すると、階乗関数の全体的な時間計算量が得られます。

この方法は、反復アルゴリズムを1行ずつ解析して複雑さを追加することにより、反復アルゴリズムの時間計算量を計算するため、反復法と呼ばれます。

反復法に加えて、さまざまなケースで他のいくつかの概念が使用されます。 たとえば、再帰的方法は、再帰的ツリーまたは置換を使用する反復解の時間計算量を計算するための優れた方法です。 時間計算量を計算するもう1つの一般的な方法は、マスターの定理です。

4. スペースコンプレキシティとは何ですか？

アルゴリズムをコンピュータで実行する場合、必然的に特定の量のメモリスペースが必要になります。 スペースの複雑さは、実行を実現するために1つのプログラムが使用するメモリの量を表します。プログラムは実行中に入力データと時間値を格納するためにメモリを必要とするため、スペースの複雑さは補助的な入力スペースです。

時間計算量と同様に、ソリューションの評価にも役立ちます。 時間計算量の場合に前に示したのと同じLandauの表記法を使用して表されます。

時間計算量と同様に、各アルゴリズムで消費されるメモリに応じて、さまざまなタイプの空間計算量があります。 一定のスペースの複雑さを持つアルゴリズムの例は、他のメモリスペースなしで同じ配列で動作するため、selectionsortです。

マージソートは、線形空間の複雑さを伴うアルゴリズムの例です。元の配列の一部で構成される多くの配列を作成する必要があります。 したがって、アレイが大きいほど、より多くのメモリスペースが必要になります。

5. スペースの複雑さを計算する方法

このセクションでは、例を使用してスペースの複雑さを計算する方法について説明します。 ここでは、配列の要素の合計を計算する例を取り上げています。

1. int sum, i 
2. while i ≤ n do 
3.     sum ← sum + a[i] 
4.     i ← i + 1 
5. end while 
6. return sum

アルゴリズムのスペースの複雑さを考えてみましょう。 ほとんどのシステムでは、整数はメモリ内でバイトのスペースを取ります。 したがって、スペースの複雑さは、割り当てられたバイト数になります。

1行目では、メモリスペースが2つの整数、つまりバイトに割り当てられています。 2行目はループを示しています。 3行目と4行目では、既存の変数に値を割り当てています。 したがって、スペースを割り当てる必要はありません。 6行目で、returnステートメントはもう1つのメモリケースを割り当てます。 したがって、バイト。

配列はアルゴリズムで整数のケースを割り当てているため、最終的なスペースの複雑さは次のようになります：。

6. 時間計算量と スペースの複雑さ

これで、時間と空間の複雑さの基本と、アルゴリズムまたはプログラムでそれを計算する方法がわかりました。 このセクションでは、これまでのすべての説明を要約し、主な違いを表に列挙します。

7. 結論

間違いなく、時間と空間の両方の複雑さは、ソリューションを評価するための2つの重要なパラメーターです。 それにもかかわらず、ハードウェアテクノロジの現在の進化により、ほとんどすべてのマシンに十分なメモリがあるため、スペースの複雑さはもはや重要ではなくなりました。 ただし、時間計算量は依然としてアルゴリズムを評価するための重要な方法です。

このチュートリアルでは、時間と空間の複雑さの背後にある理論について説明しました。 さらに、それぞれの場合の例を使用して、時間と空間の複雑さを計算する方法の手順を示しました。

最後に、これら2つの概念の主な違いを表にまとめました。