数据结构初阶---复杂度

一、数据结构前言

1.数据结构与算法

数据结构(Data Structure)：是计算机组织、存储数据的一种方式，指相互之间存在一种或多种特定关系的数据元素的集合。

算法(Algorithm)：就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。算法就是对数据进行处理的方法。

2.数据结构与数据库

数据结构--->在内存中管理、存储数据--->具有速度快、带电存储(关闭失去数据)的特点。

数据库--->在磁盘中管理、存储数据--->具有速度慢、不带电存储(关闭不会失去数据)的特点。

关于带电存储与不带电存储，简单理解就是，内存中存储数据，断电、程序关闭会销毁数据回收空间，因此称为带电存储；而不带电存储，在磁盘中存储数据，会保存数据到磁盘中，哪怕关闭程序关闭机器，数据依旧保存在了磁盘中。当我们创建一个文件，将数据写入文件，此阶段相当于内存中数据存储，关闭前进行保存，保存操作就是将数据存储在磁盘的一个过程，如果没有保存，机器因特殊情况关闭，数据相当于带电存储，关闭导致数据流失，当我们下次开机时打开文件不会有上次未保存的数据。

我们在C语言中写的通讯录其实就是一个对于顺序表的使用，用到了数据结构相关的知识。

二、复杂度

复杂度的研究无关机器硬件，算法在编写成可执行程序后，运行需要消耗时间与空间(内存)资源，因此衡量一个算法的好坏一般是从时间维度和空间维度两个层面上考虑的--->即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法运行速度的快慢；空间复杂度主要衡量一个算法运行所需要消耗的额外空间。

1.时间复杂度

时间复杂度是一个数学意义上的函数(数学表达式)，指算法中基本操作的执行次数F(N)，N只是一个符号，可以用其他符号，但一般习惯于用N表示。时间复杂度定量描述了算法的运行时间。

这个数学表达式是某条基本语句与问题规模N之间的关系式，所以时间复杂度其实是问题规模N的一个数学意义上的函数。

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

上面的代码中，关于count++，执行了多少次呢？

第一个for循环执行了N^2次，第二个for循环执行了2N次，while循环执行了10次，所以一共执行了N^2+2N+10次。

那么对于函数Func1，它的基本操作的执行次数F(N) = N^2+2N+10。

当N逐渐变大的时候，我们发现N^2所占的权重其实逐渐变大，而2N与10所带来的影响越来越小，因此对于时间复杂度而言，采用了大O渐进表示法--->选择基本操作执行次数的数学函数中影响最大的一项作为时间复杂度的函数，对于上图而言，O(N^2)就是上图中Func1函数的时间复杂度。

大O渐进表示法

所谓的渐进，实际上就是估算的意思，即省略了影响较小的函数项，保留影响最大(阶数最大)的那一项。

对于大O渐进表示法来表示时间复杂度，有以下三个标准：
①若程序操作执行次数F(N)是常数，无论是1还是100000000(CPU处理100000000次循环的速度与处理1次循环的速度差不多)，时间复杂度均为O(1)，1代表执行次数为常数。

②若程序操作执行次数F(N)是与问题规模N有关的函数表达式，那么我们保留影响最大的那一项作为该程序的时间复杂度，其余项省略。

③若程序操作执行次数F(N)是与问题规模N有关的函数表达式，我们在省略影响较小项同时，对于影响最大项的常数系数，也进行省略。如O(2*N^2)省略为O(N^2)。

下面是几个简单的能够直接求出操作执行次数的实例：

// 计算Func2的时间复杂度？
void Func2(int N)
{
 int count = 0;
 for (int i = 0; i < 2 * N ; i++)
 {
 count++;
 }
 int C = 10;
 while (C--)
 {
 count++;
 }
 printf("%d\n", count);
}

如上图F(N)=2N+10，根据大O渐进表示法--->时间复杂度为O(N)。

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

上图的F(N)=M+N，由于M与N都是未知的，因此一般而言时间复杂度为O(M+N)或O(max(M,N))，如果能够判断M与N的大小关系，那么①M远大于N--->O(M) ②N远大于M--->O(N) ③M与N差不多大小--->O(M)或者O(N)。

// 计算Func4的时间复杂度？
void Func4(int N)
{
 int count = 0;
 for (int k = 0; k < 100; k++)
 {
 count++;
 }
 printf("%d\n", count);
}

上图for循环执行100次，常数次的一个循环--->时间复杂度为O(1)，1代表常数次执行次数。同理，k<100000000也是O(1)。

那么还有一些无法简单判断出时间复杂度的代码：

const char * my_strchr ( const char * str, int character )
{
    while(*str)
    {
        if(*str == character)
            return str;
        str++;
    }
    return NULL;
}

前面学过一个函数strchr的模拟实现，在字符串中查找是否存在字符character，存在返回字符串，不存在返回NULL。那么对于这样一个模拟实现，它的时间复杂度是多少呢？我们可以判断，这个while循环是不一定走完字符长度的次数的。可能在中途查找到了字符character而直接返回，也可能开头首字符就直接返回，也有可能最后一个字符才匹配，甚至是返回空指针。因此我们发现，针对这个函数模拟实现内部的循环，无法做到准确判断时间复杂度，这个时候对于大O渐进表示法，它给出了标准：如果无法判断时间复杂度，那么根据最坏的情况进行计算时间复杂度，那么对于strchr函数的模拟实现而言，最坏的情况就是没有字符匹配而返回了空指针，这个时候相当于while循环遍历了整个字符数组，所以时间复杂度为O(N)。

综上，上图strchr模拟实现的函数的时间复杂度为O(N)。

当有些算法的时间复杂度存在最好、平均和最坏情况时：

最坏情况：任意输入规模的最大运行次数(上界)；

平均情况：任意输入规模的期望运行次数；

最好情况：任意输入规模的最小运行次数(下界)。

在实际中一般情况关注的是算法的最坏运行情况。

思路判断时间复杂度是本质

我们在实际情况中，并不是先写出代码再来判断时间复杂度，通常是，我们想出解决问题的逻辑--->思考逻辑实现的时间复杂度--->选择出时间复杂度最低的逻辑方法--->实现代码。

因此，不能只会判断简单代码、能够直接计算复杂度的代码的时间复杂度，更重要的是我们需要学会通过逻辑与思路，来判断代码的时间复杂度。

那么下面会举一些相关思路的复杂的例子：

//冒泡排序---降序
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] < arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

对于上图降序的冒泡排序函数，我们不能片面理解复杂度，认为复杂度看循环就可以了，那其实我们就把复杂度看窄了，对于简单代码，确实可以直接通过循环判断，但是一旦复杂，通过循环无法清晰得到结论，我们需要看思路：冒泡排序思路是分两大块，①n个元素排n-1趟，②每一趟交换的次数。那么我们很容易就能够发现，第一趟---交换n-1次，第二趟---交换n-2次，第三趟---交换n-3次，......第n-1趟---交换1次，那么其实对于冒泡排序而言，它整体的这个执行次数F(N)是一个等差数列n-1、n-2、n-3、......、3、2、1的和，那么就是(n-1)*n/2，那么时间复杂度就是O(n^2)。

Extra---题目---消失的数字

那么我们接下来看一个题：数组nums包含了从0--n的所有整数，但其中缺失了一个，请编写代码找出缺失的那个整数，实现Missing_Num函数即可，int Missing_Num(int* arr,int arrsize)。

如果是一个项目，给我们的任务是解决上述问题，那么我们应该想出解题逻辑思路，大致在脑海中计算思路所需要的时间复杂度，然后选择时间复杂度最低的思路，也就是最好的、速度最快的思路进行实现。

那么我们能够想到什么方法去解决这个问题呢？

①冒泡排序升序数组nums，然后遍历数组逐个与下标比较，不相等处的下标即为缺失的元素。

方法①，使用了冒泡排序，遍历数组--->F(N)=(n-1)*n/2+n=(n+1)*n/2--->时间复杂度O(n^2)。

②找单身狗1中使用过异或操作符，相同为0相异为1，我们将0-n异或，再异或数组所有元素得到的就是缺失的整数。

方法②，使用一次for循环或者使用两次(不嵌套)就可以解决问题F(N)=2N+1--->时间复杂度O(N)。

③可以0-n所有整数相加，然后减去数组中所有元素，最后的值就是缺失整数。

方法③，减数组所有元素遍历一次即可，F(N)=N--->时间复杂度O(N)。

那么如此进行分析，我们就可以排除方法①，选择方法②或者方法③来解决这个问题。

使用方法②：

int Missing_Num(int* arr, int arrsize)
{
	int ret = 0;
	for (int i = 0; i < arrsize; i++)
	{
		ret ^= arr[i];
	}
	for (int i = 0; i <= arrsize; i++)
	{
		ret ^= i;
	}
	return ret;
}

其实也可以写成一个循环：

使用方法③：

int Missing_Num(int* arr, int arrsize)
{
	int n = arrsize;
	int sum = ((n + 0) * (n + 1)) / 2;
	for (int i = 0; i < arrsize; i++)
	{
		sum -= arr[i];
	}
	return sum;
}

时间复杂度的进阶案例

二分查找函数：前提条件是，这个数组是有序数组。

// 计算BinarySearch的时间复杂度？
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-1;
 else
 return mid;
 }
 return -1;
}

那么对于一个二分查找的函数，它的时间复杂度是多少呢？二分查找每次，将需要查找的数据与数组中间的数进行比较，然后每次缩减数组一半的数据：

所以依据思想，有关于二分查找的时间复杂度为O(logN)。

阶乘递归函数：

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
 if(0 == N)
 return 1;
 return Fac(N-1)*N;
}

虽然函数内没有循环，但是是一个递归函数，函数会被多次重复调用，因此执行次数会随着传入参数的变化而增加：

所以传入参数N，其实一共就递归调用了N次函数，因此时间复杂度为O(N)。

在阶乘递归函数中加入一个for循环：

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
 if(0 == N)
 return 1;
 for(int i=0;i<N;i++)
{
    ;
}
 return Fac(N-1)*N;
}

在递归函数中加入一个有关于参数N的循环，那么我们依旧通过图解来判断这个递归函数的循环次数：

斐波那契函数的递归：

// 计算斐波那契函数的时间复杂度？
long long Fib(size_t N)
{
 if(N < 3)
     return 1;
 return Fib(N-1) + Fib(N-2);
}

依旧是函数内没有循环，只有函数递归的调用次数：

F(N)执行次数的计算是一个等比数列的和，所以时间复杂度为O(2^N)。

2^N的时间复杂度，效率太低了，因此要对递归的斐波那契函数进行修改：可以使用for循环进行前两个数累加求得下一个数的方式，这样的话时间复杂度为O(N)。

// 返回斐波那契数列的前n项
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;
}

2.空间复杂度

对于空间复杂度而言，同样采用大O渐进表示法，也同样遵循大O渐进表示法的三个准则。

空间复杂度也是一个数学表达式的函数，是对一个算法在运行过程中临时占用存储空间大小的量度。它的衡量标准不是操作的执行次数，而是在函数中为了完成任务解决问题额外创建的变量个数。

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

那么我们拿出前面的冒泡排序函数的例子：

//冒泡排序---降序
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] < arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

对于这个冒泡排序函数，我们在函数中额外创建的变量就是i、j、tmp，空间大小是能够确定的，因此空间复杂度为O(1)。

对于上面改装的斐波那契函数，它的空间复杂度是多少呢？

//空间复杂度？
// 返回斐波那契数列的前n项
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项，我们使用malloc动态开辟了一块空间，空间内有n+1个长整型的斐波那契数，那么这个空间就是属于额外开辟的空间，就会计算在空间复杂度当中，因此空间复杂度为O(N)(依据标准简化)。

对于前面的阶乘的递归函数，它的空间复杂度是多少呢？

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
 if(N == 0)
     return 1;
 return Fac(N-1) * N;
}

函数递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)，一共调用N次--->空间复杂度为O(N)。

有关递归函数空间复杂度的计算，也是空间累加，不同的是空间可以重复利用！

如下面斐波那契函数：

// 计算斐波那契函数的空间复杂度？
long long Fib(size_t N)
{
 if(N < 3)
     return 1;
 return Fib(N-1) + Fib(N-2);
}

我们在调用Fib(N-1)的时候，分裂导致会向下依次调用Fib(N-2)与Fib(N-3)，那么我们调用Fib(N-1)时创建的栈帧其实没有销毁，这个栈帧要等到Fib(N-1)计算完之后才能销毁，因此在分裂的空间利用中，存在重复的空间多次利用！

关于函数栈帧销毁与空间回收后的重复利用，我们可以用下图来做一个验证：

如图我们发现，在func1函数栈帧中创建的临时变量a的地址与在func1函数栈帧中创建的临时变量b的地址相同，说明了由于func1与func2函数的调用相差不大，系统在回收了func1的空间后将该空间给func2使用，因此a与b前后具有相同的地址！

3.常见复杂度对比

1314	O(1)	常数阶
2N+9	O(N)	线性阶
2N^2+7N+10	O(N^2)	平方阶
7log(2)N+1	O(logN)	对数阶
3Nlog(2)N+9N+9	O(NlogN)	NlogN阶
N^3+3N^2+10	O(N^3)	立方阶
2^N+8	O(2^N)	指数阶