時間の複雑さと空間の複雑さの簡単な解説

アルゴリズムの優劣は主としてアルゴリズムの実行時間と必要な記憶空間の両方から測定される.
今年はとても流行っています.薄いキーパー紫を皆さんにプレゼントします.緑を許すならいいです.殺される恐れがあります.
最後に、時間と空間の複雑さをそれぞれ説明するために、二分割検索とフィボナッチの再帰的および反復的方法を使用する.
時間複雑度:まず、時間複雑度の計算は、計算プログラムの具体的な実行時間ではなく、アルゴリズム実行文の回数です.私たちの前に複数のアルゴリズムがある場合、時間の複雑さを計算することで、どのアルゴリズムが具体的に実行されるかを判断することができます.
一般的な時間複雑度は、定数次数O(1)、対数次数O(log 2 n)、線形次数O(n)、線形対数次数O(n log 2 n)、平方次数O(n^2)、立方次数O(n^3)k次数O(n^K)、指数次数O(2^n)である.nが増加するにつれて時間の複雑さが増大し、アルゴリズムは時間が多くかかります.
計算方法①比較的高いものを選ぶ②最高のものを1③にする.定数であれば、f(n)=2*n 3+2 n+100のようなO(n)=n 3をO(1)で表す.
一般的に計算時間の複雑さは、最悪の場合の時間複雑度を計算する計算である.(1)もしアルゴリズムの実行時間が問題の規模nの増加に伴って増加しないならば、アルゴリズムの中に千個以上の文があっても、その実行時間は大きな定数に過ぎない.このようなアルゴリズムの時間複雑さは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に等しい場合は、ループ実行一回でジャンプと判定され、時間複雑度はO(1)となります.
空間複雑度の空間複雑さは、実行中に記憶空間サイズを一時的に占有するアルゴリズムのメトリックである.計算方法:①定数を無視して、②再帰的アルゴリズムの空間複雑度=再帰的深さ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)です.
湖南省の例を挙げて説明する
1:二分検索アルゴリズムの再帰的および再帰的でないことを実現する.(分析時間の複雑さと空間の複雑さ)
反復アルゴリズム

#define _CRT_SECURE_NO_WARNINGS

#include
#include
#include

int BinarySearch(int arr[], int len, int num)
{
	assert(arr);

	int left = 0;
	int right = len - 1;
	int mid;

	while (left <= right)
	{
		mid = left + (right - left) / 2;

		if (num > arr[mid])
		{
			left = mid + 1;
		}
		else if (num < arr[mid])
		{
			right = mid - 1;
		}
		else
		{
			return mid;
		}
	}

	return -1;
}



int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9 };
	int length = sizeof(arr) / sizeof(arr[0]);
	int aim = 9;
	int result;

	result = BinarySearch(arr, length, aim);

	if (result == -1)
	{
		printf("Can't find %d
", aim);
	}
	else
	{
		printf("%d at %d postion
", aim,result + 1);
	}
	

	return 0;
}

二分検索の場合、毎回元の検索内容で二分するので、時間の複雑度はO(log 2 n)となります.変数値が作成されますので、空間の複雑度はO(1)となります.
再帰的アルゴリズム

int BinarySearchRecursion(int arr[5], int lef, int rig,int aim)
{
	int mid = lef + (rig - lef) / 2;

	
	if (lef <= rig)
	{
		if (aim < arr[mid])
		{
			rig = mid - 1;
			BinarySearchRecursion(arr, lef, rig, aim);
		}
		else if (arr[mid] < aim)
		{
			lef = mid + 1;
			BinarySearchRecursion(arr, lef, rig, aim);
		} 
		else if (aim == arr[mid])
		{
			return mid;
		}
		
	}
	else
		return -1;
	
}


int main()
{
	int arr[] = { 1,2,3,5,6, };
	int sz = sizeof(arr)/sizeof(arr[0]);
	int result;

	result = BinarySearchRecursion(arr, 0, sz - 1, 4);

	if (-1 == result)
	{
		printf("Can't find it.
");
	}
	else
		printf("Aim at %d location
", result+1);
}

時間複雑度はO(log 2 n)であり、再帰ごとに変数が作成されますので、空間複雑度はO(log 2 n)です.
2:フィボナッチの数列の再帰及び再帰を実現する.(分析時間の複雑さと空間の複雑さ)
反復アルゴリズム

int FeiBoNaCciInteration(int a,int b,int num)
{
	int c;

	if (num <= 0)
		return -1;
	else if (num == 1)
		return a;
	else if (num == 2)
		return b;
	else
	{
		while (num - 2)
		{
			c = a + b;
			a = b;
			b = c;
			num--;
		}
		return c;
	}
	
}

int main()
{
	int n;
	int result;

	printf("Input n
");
	scanf("%d", &n);

	result = FeiBoNaCciInteration(2, 3, n);//               
	if (result == -1)
	{
		printf("Input Error!
");
	}
	else
	{
		printf("n is %d
", result);
	}

	return 0;
}

時間複雑度O(n)空間複雑度はO(1)である.
再帰的アルゴリズム

int FeiBoNaCciRecursion(int num)
{
	if (num < 0)
		return -1;
	if (num <= 2 && num > 0)
		return 1;
	else
		return FeiBoNaCciRecursion(num - 1) + FeiBoNaCciRecursion(num - 2);
	
}

int main()
{
	int n;
	int result;

	printf("Input n
");
	scanf("%d", &n);

	result = FeiBoNaCciRecursion(n);

	if (result == -1)
		printf("Input Error!
");
	else
		printf("Result is %d
", result);

	return 0;
}

時間の複雑さはO(^n)で、空間の複雑さはO(n)です.
コメントエリアでの質問を歓迎します.ありがとうございます.