数据结构＜1＞时空复杂度详解

什么是时间复杂度和空间复杂度

前言（算法效率）

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。
时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间.

时间复杂度的计算

时间复杂度是一个衡量算法时间的相对标准。他不是一个固定的时间例如多少分多少秒，而是一个大概的估计数值。比如同一个算法在不同的机器上运行的时间肯定不同。这时候就需要我们的时间复杂度来衡量算法的时间效率。

时间复杂度通常使用大O的渐进表示法（空间复杂度也是）

那么什么是大O的渐进表示法呢？

列举几个实例给搭建看看 O(N),O(N^2),O(1);

如上所示就是大O的渐进表示法。括号内就是算法执行的次数估计值，要记住时间复杂度计算的是执行次数
但是他不是一个准确的数字而是一个估计值，比如(N^2+2N+10)在N很大的时候除了最高次项其他的都可以忽略不计，这类似与数学中的极限思想，只保留对结果影响最大的一项。

推导法则如下：
1.若括号内是常数都写成O(1)
2.若是括号内是多项式例如O(N^2+3n+9)则只保留最高次项
3.若是最高次项的系数不为1则统一写成1

下面我们来看几个例子学习一下：

// 请计算一下Func1基本操作执行了多少次？
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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这个算法的具体执行次数是（N*N+2N+10）
而他的时间复杂度是O(N^2)

// 计算strchr的时间复杂度？
const char * strchr ( const char * str, char character )
{
while(*str != '\0')
{
if(*str == character)
return str;
++str;
}
return NULL;
}
1
2
3
4
5
6
7
8
9
10
11

要注意有的算法有最坏情况，最好情况和平均情况。比如上面这个算法是在一个字符串中寻找一个字符，最好情况就是一上来就找到了，时间复杂度是O(1)，最坏情况是遍历完了字符串才找到或者没找到时间复杂度为O(N),平均情况为O(N/2);时间复杂度一般是取最坏情况，这个在我们生活中也会用到就是预期管理，以最坏情况为标准，那么大部分情况都会超出预期。也就是让你感觉比较舒服。

所以我们计算时间复杂度一般是以最坏情况

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n;
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

上面这段代码是二分查找，每次查找都可以排除一半的元素，比如数组有N个元素我们查找了x次2^x = N所以
x = log2(N);

但是在算法中我们一般写成O(logN);

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

这是递归的时间复杂度计算。

每次递归的时间复杂度都是O(1),递归进行了N次，所以这个算法的时间复杂度是O(N);

插入一点：递归的效率在时间复杂度相同的情况下比循环低，因为递归需要创建函数栈帧，而循环不需要

//循环求斐波那契数列

#include

int main()
{
	int n = 0;
	scanf("%d", &n);
	
	int* fib = (int*)malloc(n * (sizeof(int)));

	fib[0] = 1;
	fib[1] = 1;
	for (int i = 2; i < n; i++)
	{
		fib[i] = fib[i - 1] + fib[i - 2];
	}
	for (int j = 0; j < n; j++)
	{
		printf("%d ", fib[j]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

该算法的时间复杂度是O(n);

int show(int *num,int m,int n)
{
    int x = 0;
    for(int i=0;i<m;i++)
    {
        x^=num[i];
    }
    for(int j = 0;j<n;j++)
    {
        x^=num[j];
    }
    return x;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

上面的算法时间复杂度是O(m+n)要注意我们不明确m和n的关系所以不能乱写，比如若m>>n那时间复杂度就是O(m)反之就是O(n)，如果m和n差不多那就是O(n^2) 或 O(m^2)

计算斐波那契数列的时间复杂度

int fab(int n)
{
	if (n <= 2)
		return 1;
	return fab(n - 1) + fab(n - 2);
}
1
2
3
4
5
6

递归求斐波那契数列，这个代码的时间复杂度是多少呢？

以这个图为例子，可以看到从上到下调用的次数我们假设每一层都是满的二叉树。当然右边有部分没有画出来，可以看到假设是从F（N）开始那么最后一层就是2^{(n-1)每次函数调用的执行次数都是常数次，所以总的时间复杂度就是2}0+2¹⁺²2+2^3+…2(N-1)根据等比数列求和公式（或者是错位相减法），最后这段代码的时间复杂度就是O(2^n)这是一个超级大的数，n=10就是1024，20就是100w，30就是10亿

为了了解各个时间复杂度的差异我们来看一下图

图上我们可以看到logn与1非常接近，所以这两个都是近乎最好的算法复杂度。

空间复杂度的计算

上文提到，时间复杂度实际上就是计算代码执行次数
而空间复杂度实际上就是计算变量个数

这里需要我们先记住一句话时间是累积的空间是不累积的。后面会解释的
空间复杂度也是用大O的渐进表示法。例如：

// 计算BubbleSort的空间复杂度？
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
19

形参也会计算在内，所以这段代码的变量共有5个根据大O的渐进表示法为O(1),这里要注意循环了n次并不是o（n）因为上面说到空间是不累积的，每次循环完之后变量都会销毁下一次循环在创建，可以理解为使用同一片空间。

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

递归的空间复杂度是O（n），因为每次递归都会创建一次栈帧，递归在没有递归到底的时候是不会销毁前面的栈帧的（这也就是递归太深会导致栈溢出的原因）。

//循环求斐波那契数列

#include

int main()
{
	int n = 0;
	scanf("%d", &n);
	
	int* fib = (int*)malloc(n * (sizeof(int)));

	fib[0] = 1;
	fib[1] = 1;
	for (int i = 2; i < n; i++)
	{
		fib[i] = fib[i - 1] + fib[i - 2];
	}
	for (int j = 0; j < n; j++)
	{
		printf("%d ", fib[j]);
	}
    free(fib);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

该代码的时间复杂度是O（n）因为malloc开辟的空间也要计算进去。虽然 最后释放了，但是这就类似于时间复杂度的最坏情况了，我们计算的是最多的时候创建了几个变量，占用多少内存。

oj练习

https://leetcode-cn.com/problems/missing-number-lcci/

消失的数字

这里的思路是，将给定数组的所有元素异或起来，然后再与标准的数组进行异或；因为相同数字异或(按位比，相同为0，不同为1)后为0，所以最后剩下的那个数字就是数组消失的数组。
注：相同数字异或为0
任何数字异或上0之后都不变
这里也可以用求和，给定数组求和，减去标准数组之和即是消失的数字。（有溢出的可能）

int missingNumber(int* nums, int numsSize){
    int n = 0;
    for(int i = 0;i<numsSize;++i)
    {
        n^=nums[i];
    }
    for(int j = 0;j<numsSize+1;++j)
    {
        n^=j;
    }
    return n;
}
1
2
3
4
5
6
7
8
9
10
11
12

https://leetcode-cn.com/problems/rotate-array/

旋转数组

相信大家一定能想到第一种思路就是

1.把最后一个数组元素保存起来，然后将数组元素右移一个单位，再把最后一个元素放到数组开头位置。但是这样是双层循环，时间复杂度为O（N）所以效率很低。
2.用空间换时间的思想，再创建一个数组，保存nums的后k个元素，然后再保存数组的前numSize-k个元素。这样是需要递归一次数组就可以了。时间复杂度是O(N)；
3.最好的方法是，先逆置后k个数组元素，再逆置前numSize-k个数组元素，最后再整体逆置（大神想出来的方法）时间复杂度为O（N）空间复杂度是O（1）！！！
下面我们来实现一下第三种方法。

void reverse(int *nums,int left,int right)
{
    while(left<right)
    {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        left++;
        right--;
    }
}

void rotate(int* nums, int numsSize, int k){
    if(k>=numsSize)
    {
        k%=numsSize;
    }
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-k-1);
    reverse(nums,0,numsSize-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22