技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. アルゴリズムの効率化

同じアルゴリズムの問​​題を完了するプロセスにはさまざまな方法があり、最終的な効果は同じで正確ですが、効率は異なる場合があります。
同じ場所から出発して別の場所に到着するのと同じように、その場所に行く手段は飛行機、電車、自家用車…でも、かかる時間も違いますし、経済状況も違います。

1. 複雑さの概念

アルゴリズムが実行可能プログラムに書き込まれた後、実行するには時間リソースと空間 (メモリ) リソースが必要です。したがって、アルゴリズムの品質は通常、時間と空間の 2 つの次元、つまり時間計算量と空間計算量から測定されます。
時間計算量は主にアルゴリズムの実行速度を測定し、空間計算量は主にアルゴリズムの実行に必要な追加スペースを測定します。
コンピュータ開発の初期の頃、コンピュータの記憶容量は非常に小さかった。そのため、私たちは空間の複雑さを非常に重視しています。しかし、コンピュータ産業の急速な発展により、コンピュータの記憶容量は非常に高いレベルに達しました。したがって、アルゴリズムの空間の複雑さに特別な注意を払う必要はなくなりました。

2. 複雑さの重要性

一部のゲームをプレイすると、携帯電話が非常に熱くなりますが、一部のゲームをプレイすると熱くならないことがあります。これは複雑さと切り離すことができません。携帯電話は単純なアルゴリズムを実行しており、高速に動作します。アルゴリズムが複雑なので、使用時間を確実に減らすためにフルパワーを有効にする必要があるため、熱くなります。

2. 時間計算量

定義: コンピューター サイエンスでは、アルゴリズムの時間計算量は関数式 T(N) であり、アルゴリズムの実行時間を定量的に記述します。時間計算量はプログラムの時間効率を測定するものなので、プログラムの実行時間を計算してみませんか?

• プログラムの実行時間はコンパイル環境と実行マシンの構成に関係するため、たとえば、アルゴリズム プログラムを古いコンパイラでコンパイルした場合と、新しいコンパイラでコンパイルした場合とでは、同じマシンでも実行時間は異なります。
• 同じアルゴリズム プログラムでも、古い低構成マシンと新しい高構成マシンを使用すると実行時間は異なります。
• また、時間はプログラムを作成した後にのみテストでき、プログラムを作成する前に理論的思考を通じて計算および評価することはできません。

したがって、アルゴリズムの時間割り当てを判断する際には、アルゴリズムの実行時間は考慮されず、実行される命令の数のみが考慮されます。

場合：

// 请计算⼀下Func1中++count语句总共执⾏了多少
次？
void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N ; ++ i)
{
	for (int j = 0; j < N ; ++ j)
	{
		++count;
	}
} 
	for (int k = 0; k < 2 * N ; ++ k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

観察を通して：
Func1 によって実行される基本操作の数:
T(N) = N²+ 2*N + 10

実際には、時間計算量を計算するとき、プログラムの正確な実行数を計算することは依然として非常に面倒です (プログラム コードの文が異なれば、コンパイルされる命令の数も異なります)。これ)、正確な実行数を計算することはあまり重要ではありません。時間計算量を計算する際のアルゴリズム プログラムの成長レベル、つまり、N が増加し続ける場合の T(N) の差だけを比較したいからです。 N が増加し続ける場合、定数と低次の項は結果にほとんど影響を与えないことを上で見てきました。そのため、複雑さの式は次のようになります。通常使用される Big O の漸近記法を使用します。

3. 空間の複雑さ

空間複雑度も数学的表現であり、アルゴリズムの実行プロセス中にアルゴリズムのニーズに応じて一時的に割り当てられる追加の空間です。
スペース複雑度は、プログラムが占めるスペースのバイト数ではありません。通常の状況では、各オブジェクトのサイズに大きな違いはないため、スペース複雑度は変数の数によって計算されます。
空間計算量の計算ルールは基本的に実際の計算量と同様であり、Big O の漸近表記も使用されます。
注: 関数の実行時に必要なスタック スペース (パラメーター、ローカル変数、一部のレジスタ情報などの保存) はコンパイル中に決定されるため、スペースの複雑さは主に、実行時に関数によって明示的に適用される追加スペースによって決まります。 。 もちろん
現在のコンピュータ開発においてスペースは重要な考慮事項ではありませんが、過度の無駄は避けなければなりません。無駄が多すぎると不要な問題が発生します。

4. Big O の漸近表現

Big O 記法: 関数の漸近的な動作を記述するために使用される数学記号です。
Big O 漸近記法にプッシュするためのルール:

• 1. 時間計算量の関数式 T(N) では、最上位の項のみが保持され、低次の項は削除されます。これは、N が増加し続けると、
  結果に対する低次の項の影響はますます小さくなり、N が無限大の場合は無視できます。
• 2. 最上位の項が存在し、1 でない場合は、この項の定数係数を削除します。これは、N が増加し続けると、この係数が大きくなるからです。
  結果への影響はますます小さくなり、N が無限大の場合は無視できます。
• 3. T(N) に N 関連項目がなく、定数項目のみがある場合は、すべての加法定数を定数 1 に置き換えます。

最悪の場合: 任意の入力サイズに対する最大実行数 (上限)
平均的なケース: 任意の入力サイズでの予想される実行数
最良の場合: 任意の入力サイズに対する最小実行数 (下限)
実際には、Big O の漸近表現は一般に、最悪の動作状況であるアルゴリズムの上限に焦点を当てます。

5. 計算複雑性のケース

1. Func1 関数の複雑さを計算します。

void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	} 
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	} 
	int M = 10;
	while (M--)
	{
		++count;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

時間計算量:

このコードでは、count=0 など、1 回実行するコードを省略します。
実行時間に大きな影響を与えるコードの実行数を維持する
最初のループの実行回数はN回の二重ループ実行です。いいえ
2 番目のループはループ実行回数 2 の層です。いいえ
3サイクル目は10回
実行回数の合計は T(N)=N となります。²+2*N+10
Big O は時間の複雑さを表し、小さな影響を無視して限界を考慮します
の上²)

空間の複雑さ:

Func1 関数は、スペースのサイズに適用されます。たとえば、int count = 0 は、int 型のスペース サイズに適用され、int 型のスペースにも適用されます。
これら 2 つのスペースは、追加のアプリケーション スペースなしでループ内でも使用されます。
アプリケーションスペースのサイズは一定です
Big O で表現される空間の複雑さは次のとおりです。
オー(1)

2. Fun2 の時間計算量を計算します。

void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	} 
	int M = 10;
	while (M--)
	{
		++count;
	} 
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

時間計算量:

コードの実行回数は、最初のループ (N*2) よりも大きくなります。
2 番目のループは 10 回実行されます
時間計算量を表すには大きな O を使用します。最大の影響は 2*N です。前の係数項は省略されます。
の上）

3. Func3 の時間計算量を計算する

void Func3(int N, int M)
{
	int count = 0;
	for (int k = 0; k < M; ++k)
	{
		++count;
	}
	for (int k = 0; k < N; ++
			k)
	{
		++count;
	}
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

時間の複雑さ

不明な点が 2 つあり、より大きな影響は 2 つのループにあります
最初のループは M 回実行されます
2 番目のループは N 回実行されます
どっちが大きくてどっちが小さいかは分からない数字のはずです。
O(M+N)

4. Func4 の時間計算量を計算する

void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9

時間計算量:

ここでの最大の影響はサイクルです
ループの実行回数は 100 回です
固定定数です
オー(1)

5. strchr の時間計算量を計算する

const char* strchr(const char* str, int character)
{
	const char* p_begin = str;
	while (*p_begin != character)
	{
		if(*p_begin == '0')
			return NULL;
		p_begin++;
	}
	return p_begin;
}
1
2
3
4
5
6
7
8
9
10
11

この関数によって実行される機能は、配列内の文字の添え字を見つけることです。
ここでの実行数は不明です
F(N)=1を一度に求めることが可能
中間で F(N)=N/2 を見つけることができます。
最後に見つかる場合もありますが、見つからない場合は NULL が返されます (F(N)=N)
Big O は最悪のシナリオを想定しています。
時間計算量は O(N)

6. Func5 の時間計算量を計算する

void func5(int n)
{
	int cnt = 1;
	while (cnt < n)
	{
		cnt *= 2;
	}
}
1
2
3
4
5
6
7
8

この実行回数は n のサイズに関係しますが、n 回ループするわけではありません。これは、ループ中にループ変数が 2 倍され、10 回実行された後すぐにループが終了するためです。ループ変数 cnt の値は 1024 に達します。
サイクル数を x とすると 2^バツ=n
x=logn
したがって、時間計算量は次のようになります: O(longn)

7. BubbleSor の複雑さを計算する

void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		} 
		if(exchange == 0)
			break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

この関数はバブル昇順ソートを完了します
ここにループがあります。このループは 2 レベルのネストされたループです。
ループ回数は不定です
最悪のシナリオは、外側のループが n 回実行されることです。
次に、内側のループが (n-1)+(n-2)+(n-3)+……+2+1+0 を実行します。
は等差数列であり、合計は次のようになります。

時間計算量は次のとおりです: O(N)

空間の複雑さ:

追加のアプリケーション スペースはなく、適用されるスペースは一定です。
オー(1)

8. 階乗再帰 Fac の計算の複雑さ

long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}
1
2
3
4
5
6

時間計算量:

N回再帰
したがって、時間計算量は次のようになります: O(N)

空間の複雑さ:

再帰するたびに、スペースを申請する必要があります。
N 回再帰され、N 回のスペースに適用されました。
空間の複雑さは次のとおりです: O(N)