【データ構造とアルゴリズム】アルゴリズムの複雑度π一時間の複雑度

【データ構造とアルゴリズム】アルゴリズムの複雑度π一時間の複雑度
前の文では反転というように、小さいアルゴリズムで機能を実現しました.その時の配列長は10未満です.いくつかの異なる配列がありますが、アルゴリズムが異なる配列に費やされた時間と性能が優れているとどう判断しますか?アルゴリズムの評価は主に時間の複雑さと空間の複雑さから考えられます.
時間複雑度T(n)
nは問題の規模と呼ばれ、nが変化すると時間頻度T(n)も変化していく.一般的に、アルゴリズムで基本的な動作を繰り返し実行する回数は問題規模nの関数であり、T(n)で表し、nが無限大に近い場合、T(n)／f(n)の極限値がゼロに等しくない定数である場合、f(n)はT(n)の同数関数である.T(n)＝O(f(n))と記し、O(f(n)と呼ぶ.アルゴリズムの漸進時間複雑度を時間複雑度と略称する.
上記の篇のアルゴリズムを例に説明します.

void reverse(T& array){
    int left = 0;
    int right = getArrayLen(array) - 1;
    int temp ;
    while(left < right){
        temp = array[left];
        array[left] = array[right];
        array[right] = temp;
        left ++;
        right --;
    }
}

方法体の前3行の文を実行する時は2 msと仮定します.n(array)の長さを10(n＝10)とするとwhileは5回実行するので、サイクル数はn/2.whileは1回で10 msと仮定します.だからT(n)<=n/2*10+2;計算時間の複雑さは、通常O(n)で表される.
大きなO記号O(n)
コンピュータ科学では,アルゴリズムの複雑さを解析する上で非常に有用である.
記号
名前
O(1)
定数(次数、以下同じ)
O(ロゴ＊n)
反復対数
O(ロゴn)
対数
O[(log n)^c]
複数対数
O(n)
リニア
O(n log n)
線形対数、または対数線形、擬線形、超線形
O(n^2)
平方
O(n^c)、Integer(c>1)
多項式は「代数」と呼ばれることがあります.
O(c^n)
指数は、「幾何学」と呼ばれることがあります.
O(n!)
階乗は、「組み合わせ」と呼ばれることがあります.
最後に
上の簡単な説明を通して、友達はもうその原理と特性を知っていると信じています.本人の能力は限られています.間違いを発見したり、不合理なことがあったら、指摘を歓迎します.