時間の複雑さと空間の複雑さについて簡単に説明します

一つのアルゴリズムの良し悪しは、どのように測定すればいいのだろうか.我々は通常アルゴリズムの複雑さに基づいてプログラムの複雑さを測定する.複雑度は時間複雑度と空間複雑度に分けられる.では、時間の複雑さと空間の複雑さをどのように計算するかについて議論します.
1.時間の複雑さ
時間複雑度とは,1つのアルゴリズムで基本動作を実行する回数を指す.では、時間の複雑さはどのように表現すればいいのでしょうか.
時間複雑度の大きいO漸進表現
1つのアルゴリズム文の総実行回数は,問題規模Nに関するある関数であり,f(N),Nを問題規模と呼ぶ.文全体の実行回数はT(N)とし,Nが変化するとT(N)も変化し,アルゴリズム実行回数の増加率とf(N)の増加率は同じである.T(N)=O(f(N))があり、O(f(n))を時間的複雑度のO漸進表現と呼ぶ.以下は一般アルゴリズム時間複雑度O(n)の算出方法である:(1)運転時間中のすべての加算定数を定数1で置換(2)修正後の運転回数関数において、最高次数項のみを保持(3)最高次数項係数が存在し1でない場合、最高次数項係数を除去する
次に栗を挙げます.

//          
long long fib_norec(unsigned int n)//    n      
{
    int f1 = 1;
    int f2 = 1;
    int f3=1;
    while (n > 2)
    {
        f3 = f1 + f2;
        f1 = f2;
        f2 = f3;
        n--;
    }
    return f3;
}

上記のアルゴリズムの基本的な動作はwhileループの文であり,その文はn−2回実行され,その時間的複雑度はO(n)である.上記のアルゴリズムは実行回数がわかりやすいので,再帰アルゴリズムの時間的複雑さを見てみる.

//         
long long fib_rec(unsigned int n)//    n      
{
    if (n < 2)
        return n;
    else
        return fib_rec(n - 1) + fib_rec(n - 2);
}

コードから,解F(n)が要求され,F(n−1)とF(n−2)が先に計算され,F(n−1)が計算され,F(n−3)とF(n−4)が先に計算されなければならないことが分かる.このようにして、F(1)とF(0)を先に計算しなければならないまで、F(n−1)とF(n−2)の結果を逆に推定し、F(n)が多くの繰り返し値を計算するまで時間的に大きな浪費をもたらし、アルゴリズムの時間的複雑度はNの増加に伴って指数的に増加し、時間的複雑度はO(2^n)、すなわち2のn次方である.以上の栗から,再帰アルゴリズムの時間的複雑度は,再帰回数*再帰ごとに基本操作を実行する回数が以上の2つの例を通して,一般的なアルゴリズムの時間的複雑度が計算できることをまとめた.
2.空間複雑度
空間複雑度:関数に作成されたオブジェクトの個数問題規模関数式について、一般的にはOの漸進表現で表され、時間複雑度の表現方法と同じである.次に栗を挙げて、空間の複雑さの計算方法について議論します.

//         
int bin_search_norec(int *arr, int len, int x)
{
    int left = 0;
    int right = len-1 ;
    while (left <=right)
    {
        int mid = left + ((right - left) >> 1);

        if (arr[mid] > x)
        {
            right = mid-1 ;
        }
        else if (arr[mid] < x)
        {
            left = mid + 1;
        }
        else
            return mid;//  x     
    }
    return -1;//-1     
}

上のプログラムではループが必要な回数はlog(n)(2をベース)であり,必要な補助空間は数変数の空間で定数級であるため,空間複雑度はO(1)である.次に,二分検索の再帰法の空間的複雑さを見てみる.

//        
int bin_search_rec(int *arr,int left,int right,int x)
{
    int mid = left + ((right - left) >> 1);
    while(leftif (arr[mid] > x)
        {
            return bin_search_rec(arr, left, mid - 1, x);
        }
        else if (arr[mid] < x)
        {
            return bin_search_rec(arr, mid + 1, right, x);
        }
        else
        {
            return mid;
        }
    }   
    return -1;  
}

上のコードから分かるように、毎回検索した後、次の検索範囲は元の半分になり、最悪の場合、X回ループした後に検索する数を見つけたら、2^x=n;x=log(n)(2をベースとし,以下同)の再帰回数と深さはlog(n)であり,必要な補助空間のたびに定数レベルである:空間複雑度:O(log(n))である.