アルゴリズムの複雑さについて述べる

時間の複雑さ
1.時間頻度
アルゴリズムの実行時間
2.時間の複雑さ
nをイベント規模と呼び,nが変化し続けると時間頻度T(n)も変化し,この変化法則を時間複雑度と呼ぶ.
一般的に、アルゴリズムにおける基本操作の繰返し実行回数は問題規模nのある関数であり、T(n)で表され、ある補助関数f(n)があれば、fn*c>=T(n)が一定に成立するように正常数cが存在する.T(n)=O(f(n))と表記し、O(f(n))をアルゴリズムの漸進時間複雑度、略称時間複雑度と呼ぶ.
くうかんふくざつさ
スペース複雑度(Space Complexity)は、実行中にアルゴリズムが一時的にストレージ領域のサイズを占有するメトリックです.
複雑度分析
通常、一つのアルゴリズムの複雑度はその入力量によって決まる、入力が増加するにつれて複雑度が変化する.アルゴリズムの複雑さを低減するためには,入力量を同時に考慮し,より良いアルゴリズムを設計すべきである.
実際の計算アルゴリズムの複雑さ(時間基準)
影響の少ない定数相を削除
O(1)

int aFunc(void) {
    printf("Hello, World!
");      //       1  
    return 0;       //      1  
}

//T(n) = 2       O(1)

O(n)

int aFunc(int n) {
    for(int i = 0; i

O(n^2)

void aFunc(int n) {
    //            O(n^2)
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("Hello, World!
");
        }
    }
    //            O(n)
    for(int j = 0; j < n; j++) {
        printf("Hello, World!
");
    }
}

//T(n) = n + n*(n + 1) +  n*n + n+(n+1) ， O(n^2)

判断を含むアルゴリズム

void aFunc(int n) {
    if (n >= 0) {
        //             O(n^2)
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                printf("         
");
            }
        }
    } else {
        //             O(n)
        for(int j = 0; j < n; j++) {
            printf("       
");
        }
    }
}
//O(n^2)   O(n),      O(n^2)

O(log(n))

void aFunc(int n) {
    for (int i = 2; i < n; i++) {
        i *= 2;   //     t^2 = n;     t =log(2)(n) 
        printf("%i
", i);
    }
}
T(t) = log(2)(n) = log(2n)  O(log(n))

O(2^n)

long aFunc(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}
//T(n) = T(n - 1) + T(n - 2)，            ，  n >= 1   T(n) < (5/3)^n，    n > 4   T(n) >= (3/2)^n。