アルゴリズムの複雑度解析(時間複雑度、空間複雑度)

先日、バーチャルDOMの時間の複雑さを聞かれましたが、顔がぼうっとしています.時間の複雑さは何ですか?大学のデータ構造の授業は全部寝ているかもしれません.今日は巨人の肩を見に来ました.なぜアルゴリズム分析を行いますか?

         ：
	    （CPU  ）
	    （RAM  ）
	    （    ）
         ：
	        ，          
	          

アルゴリズムの複雑さをどうやって測定しますか?

  （memory）
  （time）
     （number of steps）
       ：
	      
	     
     （Asymptotic Complexity）

アルゴリズムの運行時間は何と関係がありますか?

        （  ：         ，         ）
          （  ：6 6*10^9）
          

アルゴリズム解析の種類:

    ：             
    ：              
    ：      

アルゴリズムの分析は大局観を維持し、その基本的な考え方は:

1，             ，
2，           。

コードブロックの漸近運転を計算するには、次のステップがあります.

1，               
2，          ，   1
3，     1         ，            ，    1   1       1*n，
           ，        ，  1*n*m
4，          ，          ，           。
                                                                                                                      

   				    		  

  （Constant）		O(1) 		        ，           。n = 1,000,000 -> 1-2 operations 
  （Logarithmic）	O(log2 n) 	              n      log2 (n)。n = 1,000,000 -> 30 operations
  （Linear）	 	O(n)		              n    。n = 10,000 -> 5000 operations
  （Quadratic）	O(n2)		              n         。n = 500 -> 250,000 operations
  （Cubic）	    O(n3)		              n        。n = 200 -> 8,000,000 operations
  （Exponential）	O(2n)
					O(kn)
					O(n!)		      ，     。n = 20 -> 1048576 operations        

注1:速い数学の思い出、loba=yは実はay=bです.ですから、ロゴ24=2は22=4です.同じロゴ28=3です.23=8です.log 2 nの成長速度はn＝8の場合、log 2 n＝3より遅いという.注2:通常は10を底とする対数を常用対数といいます.簡単にするために、Nの常用対数log 10 Nは簡単にlg Nを作ります.例えば、log 10 5はlg 5をします.注3:通常は無理数eを底にした対数を自然対数といいます.便利さのために、Nの自然対数loge Nは簡単にln Nを作ります.例えば、loge 3はln 3をします.注4:アルゴリズム導論では、マークlg n=log 2 n、つまり2を底とする対数を採用しています.対数の底を変えるのは対数の値を定数の倍に変えただけです.だから、これらの定数因子を気にしないときは、O記号を使うように「lg n」という記号をよく使います.コンピューター関係者はしばしば数字の底をとるのが自然だと思っています.多くのアルゴリズムとデータ構造は問題を2点取ることに関連しています.O(1)
時間複雑度の時間複雑度の計算は、プログラムの具体的な実行時間を計算するのではなく、アルゴリズム実行文の回数です.計算方法:①相対成長の一番高い項を選ぶ②最高項の係数はいずれも1③になる.定数ならば、f(n)=2*n^3+2 n+100のようなO(n)=n^3のようなものをO(1)で表すと、一般的に計算時間の複雑さは最悪の場合の計算時間の複雑度の計算になります.アルゴリズムに千以上の語句があっても、実行時間は大きな定数にすぎない.このようなアルゴリズムの時間複雑さはO(1)である.

int x=1;
while (x <10)
{
    x++;
}

アルゴリズムの実行回数は10であり、時間の複雑さでO(1)と表現される定数である.
(2)いくつかの循環文がある場合、アルゴリズムの時間複雑度は、ネスト層数が最も多い循環文の中で最も内層文の頻度f(n)によって決定される.

for (i = 0; i < n; i++)
{
    for (j = 0; j < n; j++)
    {
        ;
    }
}

このアルゴリズムforループは、最外層サイクルを1回実行するごとに、内層サイクルはn回実行され、実行回数はnによって決定され、時間複雑度はO(n^2)である.
(3)サイクルはnだけでなく、サイクル実行に満足する判定条件にも関連している.

int i=0;
while (i < n && arr[i]!=1)
{
    i++;
}

このサイクルでは、arr[i]が1に等しくなければ、時間複雑度はO(n)である.arr[i]が1に等しいとサイクルが実行できなくなり、時間の複雑さは0です.
空間複雑度の空間複雑さは、実行中に記憶空間サイズを一時的に占有するアルゴリズムのメトリックである.計算方法:①定数を無視して、②再帰的アルゴリズムの空間複雑度=再帰的深さN*が毎回再帰的に必要な補助空間③単スレッドでは再帰的に運行時スタックがあり、再帰的に最も深いそのスタックによって消費される空間の個数を求めています.再帰的に最も深い空間は再帰的にその再帰的過程を受け入れるのに十分です.例えば:

int a;
int b;
int c;
printf("%d %d %d 
",a,b,c);

その空間複雑度O(n)＝O(1);

int fun(int n,)
{
	int k=10;
	if（n==k)
		return n;
	else
		return fun(++n);
}

再帰的に実現して、fun関数を呼び出して、毎回1つの変数kを作成します.n回呼び出し、空間複雑度O(n*1)=O(n)です.
大男を拝む～～https://www.cnblogs.com/TangBiao/p/5856695.html https://blog.csdn.net/halotrriger/article/details/78994122