時間の複雑さを理解するための文章です

時間の複雑さを理解するための文章です
もしあなたがまだどのように時間の複雑さと空間の複雑さを計算するかを心配しているならば、あなたは場所に来ました!
名詞解釈(退屈な解釈、文章の完全性のため):
コンピュータ科学では、時間複雑性、時間複雑度とも呼ばれ、アルゴリズムの時間複雑度は関数であり、アルゴリズムの実行時間を定性的に記述する.これはアルゴリズム入力値の文字列の長さを表す関数です.時間複雑度は,この関数の低次項と初項係数を含まない大きなO記号で記述されることが多い.この方式を用いる場合,時間複雑度は漸近的と呼ぶことができ,すなわち入力値の大きさが無限に近づく場合を考察する.
一.時間の複雑さの表現方法
実はアルゴリズム(コード)の実行効率、アルゴリズムコードの実行時間です.次の簡単なコードを見てみましょう.

int sumFunc(int n) {
	int num = 0; 		//     
	for (int i = 1; i <= n; ++i) {	//   n 
		num = num + i;			   //   n 
	}    
    return num;
}

各行のコードの実行時間をtとすると、このコードの時間は(2 n+2)*tである
これにより、コード実行時間T(n)は、コードの実行回数に比例する!
次の例を見てみましょう

int sumFunc(int n) {
	int num = 0;		//     
	for (int i = 1; i <= n; ++i) { 			//   n 
		for (int j = 1; j <= n; ++j) { 		//  n*n 
			num = num + i * j;			   //   n*n 
		}
	}
}

同じように、このコードの実行時間は(2 n*n+n+1)*tですが、文句はありませんか?後ろを見続けて!

注意:データ構造/アルゴリズムでは、通常、T(n)を用いてコード実行時間を表し、nはデータ規模の大きさを表し、f(n)はコード実行回数の統合を表すので、上記の例はf(n)=(2 n*n+1)*tと表すことができ、実は総和を求める式であり、O(大文字O)はコード実行時間がf(n)に比例することを表す.

上記の2つの例から,コードの実行時間T(n)は行ごとのコードの実行回数nに比例し,この法則をT(n)=O(f(n))という式にまとめた.
したがって、第1例のT(n)=O(2 n+1)、第2例のT(n)=O(2 n*n+n+1)は、時間複雑度表現法、すなわち大O時間複雑度表現法である.
しかし、大O時間複雑度は、コードの真の実行時間を具体的に示すものではなく、データ規模の増加に伴うコード実行時間の変化傾向を示すものであるため、漸進時間複雑度、略称時間複雑度とも呼ばれる.
テイラーの公式とは反対に、もういい、どこへ行ったのか...
nがますます大きくなると,式中の低次,定数,係数の3つの部分はその成長傾向に影響を及ぼさないので,それらを直接無視して最大のレベルを1つだけ記録すればよいので,上記2つの例の実際の彼らの時間複雑度はT(n)=O(n),T(n)=O(n*n)と記すべきである.
大体どういうことなのかわかると思いますが、どうやって計算するか見てみましょう.
二.時間の複雑さの分析と計算方法
(1)サイクル数が最も多い原則
nがますます大きくなると,式中の低次,定数,係数の3つの部分はその成長傾向に影響を及ぼさず,直接無視し,最大のレベルを1つだけ記録すればよいと述べた.したがって,時間の複雑さを計算する際には,ループ回数が最も多いコードに注目するだけでよい.

int sumFunc(int n) {
	int sum = 0;     //  1 ，    
	for (int i = 0; i < n; i++) {
		sum += i;  	//          ，     n ，         O(n)
	}  
	return sum;		//  1 ，    
}

(2)加算の原則

int sumFunc(int n) {
	int sum = 0;     //   ，  
    for (int i = 0; i < 99; i++) {
		sum += i;	//  100 ，     ，  
	}  
    
	for (int i = 0; i < n; i++) {
		sum += i;	//  n 
	}  
    
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++) {
			sum += i;	//  n*n 
		}
	}
	return sum;
}

上記の例では,最大の2ブロックのコード時間複雑度はそれぞれO(n)とO(n*n)であり,その結果はT(n)=O(n)+O(n*n)であるべきであり,その中で最大のレベルをとるため,セグメント全体のコードの複雑度はO(n*n)である.
したがって,最大レベルのコード時間複雑度=総時間複雑度と結論した.
(3)乗算の原則
ネストされたコードの複雑さは、ネストされた内外のコードの複雑さの積に等しい

void Func1(int n) {
	for (int i = 0; i < n; i++) {
		Func2(n);	//  n ，      Func2    n 
	}
}
void Func2(int n) {
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		sum += 1;	//  n 
	}
}

従って,このコード時間複雑度はO(n)*O(n)=O(n*n)=O(n*n)である.
同様に,いずれかのnをmに置き換えると,その時間的複雑さはO(n*m)である.
三.よく見られるいくつかの時間の複雑さ
(1)O(1)定数レベル時間複雑度

void Func(void) {
	for (int i = 0; i < 100; i++) {
		printf("hello");	//     ，     ，  O(1)
	}
}

void Func(void) {
	printf("hello");
	printf("hello");	
	printf("hello");
    //     ，    O(1)
}

O(1)はコードが1行しかないというわけではありません.この1は定数を表しています.以前1万行あったとしてもO(1)です.固定されているので変化しません(つまり定数)ので、定数級の複雑度コードはO(1)と表記されています.
(2)一般的なO(n)複雑度

void Func(int n) {
	for (int i = 0; i < n; i++) {
		printf("hello");
	}
}

言うまでもないでしょう.続けて!
(3)O(logn)、O(nlogn)、これはちょっと難しい!
まず、l o g a(b)∗l o g c(a)=l o g c(b)loga(b)*logc(a)=logc(b)loga(b)∗logc(a)=logc(b)式を覚えておきましょう.例を見てみましょう.

void Func(int n) {
	for (int i = 1; i < n; i++) {
		i = i * 2;
	}
}

i=i*2という行のコードの実行回数が最も多いことがわかりますが、いったい何回実行されたのでしょうか.
1回目i=2、2回目i=4、3回目i=8...
x回実行されたとすると、xの値は、x=l o g 2(n)x=log 2(n)x=log 2(n)x=log 2(n)上記コードの2を3に変更すると、xの値、すなわち、x=l o g 3(n)x=log 3(n)x=log 3(n)x=log 3(n)もちろん、logの基数が何であれ、eであれ、10であれ、l o g(n)log(n)log(n)log(n)と表記されるのはなぜですか.変換式から計算できる:l o g 3(n)=l o g 3(2)∗l o g 2(n)log 3(n)=log 3(2)*log 2(n)=log 3(n)=log 3(2)∗log 2(n)変換後、log 3(2)は実は定数であり、無視されていることがわかる!このゲームでは、logはデフォルトで2をベースにしているので、すべてO(logn)と表記します.

void Func(int n) {
	for (int i = 0; i < n; i++) {
		Func2(n);		//  n ，    ，      logn 
	}
}
void Func2(int n) {
	for (int i = 0; i < n; i++)
	{
		i = i * 2;		//  logn 
	}
}

だからこのO(nlogn)もよく理解できたのでしょう!
夜中のコードワードは腰が痛くて背中が痛くて、その他は余計なことを言わないで、一反三を挙げてあなたはできて、好きなら少しいいでしょう!