【数据结构】算法复杂度

数据结构

数据结构：是计算机存储和组织数据的方式。
比如打开一个网页，我们看到的文字就是数据，这些数据需要用一个结构来把他管理起来，我们称之为：数据结构

算法

就是定义一系列的计算步骤，用来将输入的数据转换成输出结果。

算法编写成可执行程序后，运行时会产生时间与空间的消耗，衡量一个算法的好坏就是从时间和空间两个维度来衡量的。

复杂度

如何衡量一个算法的好坏：

• 看算法的时间复杂度
• 看算法的空间复杂度（在计算机发展早期，内存空间有限，所以十分在意空间复杂度，但随着计算机的发展，到现在，已经不用担心计算机的内存空间问题了）

大o渐进表示法

时间复杂度
（衡量程序的效率）
定义：在计算机科学中，时间复杂度是一个函数式T(N)。
时间复杂度不能给出一个确切的时间，因为时间复杂度受到：

• 编译环境和机器配置的影响
• 并且时间只能程序写好后测试，不能写程序前通过理论计算评估
  
  比如这是在vs debug下运行得出的时间

这是在vs release下运行得出的时间。(clock函数包含在time.h头文件下)

来个例子，理解一下：

计算Func2的时间复杂度，

再来一个例子巩固一下：

时间复杂度存在最好的情况、最坏的情况和平均情况，大o渐进表示法在实际中一半情况关注的是时间复杂度最坏的情况。

计算下列这段代码的时间复杂度

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

（取的都是最坏的情况）

指对互化那一步，需要注意一下，当n接近无穷大的时候，底数的大小对结果影响不大，因此，一般情况不管底数是多少，都可以省略不写。

空间复杂度

空间复杂度 (Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度
所以，空间复杂度算的是变量的个数

空间复杂度计算规则基本跟时间复杂度类似，也使用大o渐进表示法。

注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好
了，因此，空间复杂度主要通过函数在运行时显示申请的额外空间来决定。

计算下列代码的空间复杂度：

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