時間の複雑さはどう計算しますか?時間の複雑さはどう計算しますか?

(1)アルゴリズムの基本的な語句を探し出す.
 
アルゴリズムで実行回数が一番多いのは基本的な語句で、通常は一番内側の循環体です.
 
⑵基本語句の実行回数の桁を計算する.
 
f(n)の最高乗数を正確に保持するだけで、低いべき乗と最高乗の係数は無視できます.
 
(3)使用が大きいΟ記号はアルゴリズムの時間性能を表します.
 
基本語句の実行回数の桁を大きくします.Ο記号の中
 
アルゴリズムにネストされたループが含まれている場合、基本的なステートメントは通常、最も内側の循環体であり、アルゴリズムに並列のサイクルが含まれている場合、並列ループの時間複雑度を加算する.たとえば:
 
for(i=1;i==n;i+)
x＋＋＋
 
for(i=1;i==n;i+)
for(j=1;j==n;j+)
x＋＋＋;
 
最初のforサイクルの時間の複雑さはΟ(n)2番目のforサイクルの時間の複雑さは、Ο(n²),アルゴリズム全体の時間複雑さはΟ(n＋n)²)=Ο(n²).
注、加算の原則:T(n)=O(f(n)+O(g(n)=O(max(fn,gn)
 
一般的なアルゴリズムの時間の複雑さは、小さい時から順に次のようになります.
 
　　Ο(1)＜Ο(ロゴ2 n)＜Ο(n)＜Ο(nlog 2 n)＜Ο(n²)＜Ο(n³)＜…＜Ο(2^n)＜Ο(n!)
 
Ο(1)基本語句の実行回数を示す定数は、一般的にアルゴリズムに循環語句が存在しない限り、その時間の複雑さはΟ(1)Ο(ロゴ2 n)、Ο(n)、Ο(nlog 2 n)、Ο(n 2)とΟ(n 3)多項式時間といい、Ο(2 n)とΟ(n!)は指数時間と言います.コンピュータ科学者は前者が有効アルゴリズムと考えられています.これらの問題をP種問題と呼び、後者をNP問題と呼びます.
 
 
 
一つの循環に対して、循環体の時間複雑度はO(n)であり、循環回数はmであると仮定すると、これは
サイクルの時間複雑度はO(n)である.×m)
 

void aFunc(int n) {

　　for(int i = 0; i < n; i++) { //       n

　　printf("Hello, World!
"); //           O(1)

　　}
}

 
この時の時間複雑度はO(n)です.× 1)すなわちO(n)です
複数のサイクルに対して、循環体の時間複雑度はO(n)であり、各サイクルのサイクル数はそれぞれa,b,c…であると仮定すると、このサイクルの時間複雑度はO(n)である.×a.×b×c…)分析する時は、これらのサイクルを内側から外側に分析するべきです.

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

 
この時の時間複雑度はO(n)です.× n× 1)は、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!
");
}
}

 
この時の時間複雑度はmax(O(n^2)、O(n)で、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("       
");
}
}
}

 
この時の時間複雑度はmax(O(n^2)、O(n)で、O(n^2)です.
時間複雑度分析の基本的な戦略は、内向的な外部分析から、最も深いところから分析を開始することである.