[データ構造]プログラム複雑度-空間複雑度、時間複雑度

1️⃣ Program Complexity

定義

プログラムが使用するメモリ容量とプログラムを実行する時間を測定することでパフォーマンスを表示

✅ Space Complexity : S(P)

S(P) = Fixed space(c) + Variable space (Sp(I))

Fixedspace(静的空間消費):c

空間

、入出力サイズに関係なく

実プログラムコード記憶空間

プログラム内で宣言された変数サイズ

サイズの物理空間(ex.struct,char.)を予知できる

可変空間(動的空間消費):Sp(I)

入出力空間

のトラブルシューティングプロセス、すなわち、実行時にインスタンスによって決定される空間

構造変数のspace+Recursionによって生成されたspace

インスタンスが

にどのように変化するか

ex.関数呼び出しが多ければ多いほど、空間消費が大きくなる

✅ Time Complexity : T(P)

T(P) = Compile time (Tc) + Run time(Tp)
ex.nプログラムの実行時複雑性

sum = a + b;
sum = sum - 1;
//덧셈 (1) + 뺄셈 (1) + 저장 (2) + 로드 (3) ⇒ T(P) = 1 + 1 + 2 + 3 = 7

💡 運転時間(Run Time)推定方法の問題は機器に関係なく大きくない