時間の複雑さと空間の複雑さ

1.時間の複雑さ

                        ，            ，       。                       。  T(n)。
     ，                   n     ， T(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)。

2.空間の複雑さ
一つのプログラムの空間複雑度とは、一つのプログラムを実行するために必要なメモリの大きさです.プログラムの空間複雑さを利用して、プログラムの実行に必要なメモリの数を予め見積もることができます.プログラム実行時には、自分が使用するコマンド、定数、変数、および入力データを格納する必要があるほか、データを操作するワークユニットや、現実計算に必要な情報を格納するための補助空間が必要です.プログラム実行時に必要な記憶空間は、以下の2つの部分を含みます.　　
(1)固定部分.この部分の空間の大きさは、入出力データの個数の多少、数値とは無関係です.主に指令空間(すなわちコード空間)、データ空間(定数、単純変数)などが占める空間を含む.この部分は静的空間に属する.
(2)可変空間、この部分の空間は主に動的に割り当てられた空間、及び再帰的なスタックに必要な空間などを含む.この部分の空間サイズはアルゴリズムと関連している.
アルゴリズムに必要な記憶空間はf(n)で表される.S(n)＝O(f(n))ではnが問題の規模であり、S(n)は空間複雑度を表す.