初阶数据结构

第一章 时间复杂度和空间复杂度

前言

本系列文章，将基于C语言实现一些初阶的数据结构，目的是帮助大家熟悉C语言的同时能够入门数据结构。

一、时间复杂度

1、什么是时间复杂度？

时间复杂度，顾名思义，计算的是代码运行所花费的时间。但是我们知道，一个程序是在电脑上运行的，而电脑不同，同一个程序的运行时间也是不同的。同样的一套程序，我们用十年前的电脑和现在的电脑分别运行，最终的结果肯定是不同的。
所以，此处所说的时间复杂度并不是真正的代码运行所需的时间，而是一个程序中 代码所运行的次数 。然后将这个次数写成一个 数学函数表达式。此时，这个表达式就是这个程序的时间复杂度。

例如下面代码：

#include<stdio.h>
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		printf("%d ",i);
	}
	int m=10;
	while(m--)
	{
		printf("hehe\n");
	}
	return 0;
}

我们来算一算上面代码的运行次数，即时间复杂度。

在计算代码的运行次数的时候，我们一般忽略掉循环的头部和尾部。
所以，我们通过上面的图示我们发现，这个程序的时间复杂度为：F（n）= n+13。

2、大O的渐进表示法

我们看下面的代码：

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++;
	}
	printf("%d\n",count);
}

我们计算一下上面代码的执行次数：

我们发现最终的运行次数为：F(n)=N*N+2N+13
我们不妨给这里的N进行赋值操作：

• N=10 F(N)=133
• N=100 F(N)=10213
• N=1000 F(N)=1002013
  我们发现随着我们N数值的增长，N*N的占比越来越大，剩余项的大小完全可以忽略掉。
  所以我们此时只需要保留该函数表达式中的最高次项，其余完全可以忽略掉。基于这种想法，这里就出现了一种方法叫做大O渐进表示法，也可以成为大O记法。

大O记法的方式：

- 仅仅保留最高次项。

- 最高次项的系数为1。

- 假设代码的运行次数为常数，那么统一记作O(1) 。

那么上述代码的运行次数的函数表达式可以简化为：O(N²)

另外有些时候，算法的运行次数是不确定的，例如我们利用遍历的方式在长度为N的数组中寻找一个数字，那么运气好的话，我们要找的数字就是第一个元素，此时算法的复杂度是O(1)。倘若我们运气不好的话，我们的要找的元素就是最后一个元素。此时我们算法的时间复杂度就是O(N)。
那么我们在最坏和最好的情况之间取一个平均值，即N/2，但我们利用大O记法记录时，依旧是O(N)。

从上面这个例子中，我们就能发现，我们算法的时间复杂度可以分为三种情况：

• 最坏情况：任意输入规模的最大运行次数(上界)
• 平均情况：任意输入规模的期望运行次数
• 最好情况：任意输入规模的最小运行次数(下界)

3、常见的时间复杂度例题

例一

void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
 ++count;
}
int M = 10;
while (M--)
{
 ++count;
}
printf("%d\n", count);
}

例二

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("%d\n", count);
}

例三

void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
 ++count;
}
printf("%d\n", count);
}

例四

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;
}
}

例五

int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
while (begin < end)
{
 int mid = begin + ((end-begin)>>1);
 if (a[mid] < x)
 begin = mid+1;
 else if (a[mid] > x)
 end = mid;
 else
 return mid;
}
return -1;
}

例六

long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}

例七

long long Fibonacci(size_t N)
{
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}

我们发现上面的题目中，很多题可以从表面上看出来其时间复杂度，但是有一些题目，例如：冒泡排序、斐波那契、二分查找等等算法，需要我们通过其背后的思想，通过画图等方式算出其时间复杂度，不能想当然。

二、空间复杂度

1、什么是空间复杂度？

空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，空间复杂度不是程序占用了多少字节，而是创建变量的个数。空间复杂度的表示方法依旧采用大O渐进表示法。

2、例题：

（1）例一：

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;
	}
}

分析：

我们来分析一下上述代码：
这个算法是为了实现排序。无论采用什么排序算法，函数中的形参都是存在的。所以形参并不是我们为了实现这个算法而创建的。那么为了实现冒泡排序的算法，我们临时创建的变量有图中的三个。注意：for循环内的exchange不断地重复创建，只算一次。我们可以理解成这个变量在循环的过程中不断地创建销毁，使用的都是一块空间。综上，这个代码的是时间复杂度是O(1)

（2）例二：

// 计算阶乘递归Factorial的空间复杂度？
long long Factorial(size_t N)
{
	return N < 2 ? N : Factorial(N-1)*N;
}

（3）例三：

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;
}

（4）例四：

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
	if (N < 3)
		return 1;

	return Fib(N - 1) + Fib(N - 2);
}

我们发现斐波那契函数递归展开来以后是非常庞大的。呈现指数型增长！而每个函数的内部的空间复杂度都是O(1)。难道空间复杂度是
O（2ⁿ）吗？其实为了节约空间，系统不会直接展开所有，而是如图中的绿线所示，每次展开一条递归路线，当这个递归路线到底销毁后再开启另外一条。而每一条的空间复杂度是O（N）* O(1)=O(N)。而这些空间是重复利用的。所以递归最终的空间复杂度是 O(N)