数据结构-复杂度_复杂度数据结构

算法效率

算法效率分为两种：第一种是时间效率，第二种是空间效率。时间效率就是时间复杂度，空间效率就是空间复杂度。时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，随着科技的发展，计算机的存储容量达到了很高的程度，我们如今不需要特别关注一个算法的空间复杂度了。
1

时间复杂度

概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行消耗的时间，从理论上说是算不出来的，只有你把你的程序放在机器上跑起来，才能知道。每段代码都上机会很麻烦，所以出现了时间复杂度这个分析方法。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
1

大O的渐进表示法

推导大O阶方法：
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中，只保留最高阶项。
3。如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。


有些算法的时间复杂度存在最好、平均和最坏情况
比如在一个数组（N个元素）中找到要找的字符
最好情况：一次就找到
平均情况：N/2次找到
最坏情况：N次找到
在实际情况中关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度是O(N)
1
2
3
4
5
6
7
8
9
10
11
12

void Func(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 < N; k++)
	{
		count++;
	}

	int M = 10;
	while (M)
	{
		count++;
	}

	printf("%d\n", count);
}

int main()
{
	int n = 0;
	scanf("%d\n", &n);
	Func(n);

	return 0;
}
//用函数表示时间复杂度就是：F(N)=N*N+N+10，根据规则时间复杂度就是O(N^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

void Func(int N)
{
	int count = 0;
	for (int i = 0; i < 2 * N; i++)
	{
		count++;
	}

	int M = 10;
	while (M--)
	{
		count++;
	}

	printf("%d\n", count);
}
//F(N)=2*N+10,时间复杂度是O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void Func(int N,int M)
{
	int count = 0;
	for (int i = 0; i < N; i++)
	{
		count++;
	}

	for (int j = 0; j < M; j++)
	{
		count++;
	}

	printf("%d\n", count);
}
//F(N)=N+M，时间复杂度是O(N+M)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void Func()
{
	int count = 0;
	for (int i = 0; i < 100; i++)
	{
		count++;
	}
	printf("%d\n", count);
}
//F(N)=100,时间复杂度是O(1)
1
2
3
4
5
6
7
8
9
10

void BubbleSort(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 0;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				flag = 1;
			}
		}
		if (flag == 0)
			break;
	}
}
//多项式最高项是N^2,所以时间复杂度是O(N^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void BinarySearch(int* a, int n, int x)
{
	assert(a);
	int start = 0;
	int end = n - 1;
	while (start < end)
	{
		int mid = start + (end - start) / 2;
		if (a[mid] < x)
		{
			start = mid + 1;
		}
		else if (a[mid] > x)
		{
			end = mid - 1;
		}
		else
			return mid;
	}
	return -1;
}
//N/2/2/2/....2=1,用对数表示就是log以2为底N的对数，习惯上用logN表示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

递归

递归算法的时间复杂度=递归次数*每次递归函数中调用次数
1

long long Factorial(size_t N)
{
	return N < 2 ? N : Factorial(N-1) * N;
}
//F(N)=N*1,时间复杂度是O(N)
1
2
3
4
5

long long Fibonacci(size_t N)
{
	return N < 2 ? N : Fibonacci(N-1) + Fibonacci(N-2);
}
//F(N)=2^N-1,时间复杂度是O(2^N)
1
2
3
4
5

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度算的是变量的个数，用大O渐进表示法。
1

void BubbleSort(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 0;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				flag = 1;
			}
		}
		if (flag == 0)
			break;
	}
}
//没有开辟新的数组，变量个数为4，所以空间复杂度为O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

long long Fibonacci(size_t N)
{
	return N < 2 ? N : Fibonacci(N-1) + Fibonacci(N-2);
}
//函数在调用结束后空间自动销毁，所以空间复杂度为O(1)
1
2
3
4
5

递归的空间复杂度

递归算法的空间复杂度：递归的深度*每次递归创建变量的个数
1

long long Fibonacci(size_t N)
{
	return N < 2 ? N : Fibonacci(N-1) + Fibonacci(N-2);
}
//递归调用了N次，空间复杂度就是O(N)
1
2
3
4
5

long long* Fibonacci(size_t n)
{
if(n==0)
return NULL;
long long * fibArray =
(long long *)malloc((n+1) * sizeof(long long));
fibArray[0] = 0;
fibArray[1] = 1;for (int i = 2; i <= n ; ++i)
{
fibArray[i ] = fibArray[ i - 1] + fibArray [i - 2];
}
return fibArray ;
}
//算法开辟了N+1个空间，空间复杂度是O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14