アルゴリズムの時間と空間の複雑さ

一、アルゴリズムの時間複雑度
定義:一般的に、アルゴリズムで基本的な動作を繰り返し実行する回数は問題規模nの関数であり、T(n)で表し、nが無限大に近い場合、T(n)の限界値はゼロに等しくない定数である.f(n)はT(n)の同数関数である.T(n)＝O(f(n))と記し、O(f(n)と称する.アルゴリズムの漸進時間複雑度(Oは数量レベルの符号)であり、時間複雑度と略す.一つのアルゴリズムの中のステートメントの実行回数をステートメントの頻度または時間の頻度と呼び、T(n)と表記します.
1.複雑度はO(1)

Temp=i;i=j;j=temp;

以上の3つの単語句の頻度はいずれも1であり、このプログラムの実行時間は定数であり、問題の規模nに関係ない定数である.アルゴリズムの時間複雑さは定数次数であり,T(n)＝O(1)と記した.アルゴリズムの実行時間が問題規模nの増加とともに増加しない場合、アルゴリズムに千個以上の語句があっても、その実行時間は大きな定数にすぎない.このようなアルゴリズムの時間複雑さはO(1)である.
2.複雑度はO(n^2)

sum=0；                 （  ）
for(i=1;i<=n;i++)       （n  ）
for(j=1;j<=n;j++)（n^2  ）
sum++；       （n^2  ）

解:T(n)=2 n 2+n+1=O(n^2)
3.複雑度はO(n)

a=0;
b=1;                      ①
for(i=1;i<=n;i++){   ②  
    s=a+b;　　　　③
    b=a;　　　　　④  
    a=s;　　　　　⑤

語句1の頻度:2,語句2の頻度:n,語句3の頻度:n-1,語句4の頻度:n-1,語句5の頻度:n-1,T(n)=2+n+3(n-1)=4 n-1=O(n)
4.複雑度はO(log 2 n)

i=1;        ①
while (i<=n)
    i=i*2;  ②

語句1の頻度は1で、語句2の頻度はf(n)とすると、2^f(n)<=nとなる.f(n)<=log 2 nは最大値f(n)=log 2 n,T(n)=O(log 2 n)をとります.
二、アルゴリズムの空間複雑度
時間の複雑さと同様に、空間の複雑さとは、アルゴリズムがコンピュータ内で実行されるときに必要な記憶空間のメトリックである:S(n)＝O(f(n))))
参考文献:https://blog.csdn.net/wzj_110/articale/detail/79782124https://blog.csdn.net/kangkang_hacker/articale/detail/80904695