数据结构1：时间复杂度与空间复杂度_(3n+2)(4n+4)=

目录

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

时间复杂度：

基本概念：

大O的渐进表示法：

常见时间复杂度计算举例：

空间复杂度：

复杂度的oj练习：

---

 我们基本在每一道编程题里面都能看见这下面两个东西出现，最开始看见这两兄弟的时候我们可能会非常疑惑，这俩究竟是什么来头？好像我能不能OJ也不管这两兄弟什么事啊

 那么就引出来我们下面的问题：

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

引言：我们平常使用的手机其实包含了这两个概念，我们希望手机的运算能力不仅能越来越快，重量也能越来越轻，在程序里，判断一个算法的好坏则对应的就是时间复杂度和空间复杂度的基本概念。（此处仅为概述，细致理念依然有所差别）

 那么我们以类比衡量好手机的标准来衡量一个好的程序就应该是算的快，空间占的少。

对应的概念就是时间复杂度与空间复杂度。

时间复杂度：

基本概念：

我们时间复杂度是一个函数，但这个函数并不是程序中的函数而是数学中的函数表达式，但这段函数表达式并不能完美的呈现算法的计算速度，因为是每个机器的计算速度是不一样的，所以，时间复杂度指的是一个算法所花费时间与其中语句执行次数。算法中的基本操作的执行次数，为算法的时间复杂度。

找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度

比如如下这段程序：

// 请计算一下Func1中++count语句总共执行了多少次？
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);
}    

所以，该算法的基本操作次数为：

 借助这个函数表达式，我们可以轻松的计算出每个算法的基本操作执行数，但其实知道这个并没有什么用，因为次数在算法的层面并不完全确认时间复杂度，我们只需要大概的执行次数就行。

简而言之，我们人为计算的时间复杂度更像是期望值与推导值，而非一段程序运行起来真实所可以计算得到的时间。

那么在这里，我们使用大O的渐进表示法来求取时间复杂度。

大O的渐进表示法：

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号

可以借助下面的这个表达式来更好的理解一下：

---

推导方法：

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

使用大O的渐进表示法以后，F(N)的时间复杂度为：

O(N^2)

推导过程如下：

那么我们带一些N的值进去康康：

N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)

例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

其实如果接触过高数的话就可以很容易发现，整个渐进式表示法的思想内核其实和求取极限的思想有些相像，我们 一般将最坏情况作为重点，并依次为基础计算其他的表达式是否可以对整个表达式造成影响。说人话就是：假如我的数据已经是几千兆几百万兆了，那么我加几千万对于整个数据其实也差不多，近似于于没有增加。最坏情况就是这种思想。

---

常见时间复杂度计算举例：

事先声明：请不要想当然的去数循环

1.

// 计算Func2的时间复杂度？
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);
}

答案：O（N）

与求取极限的思想相同，我们先求出来整个执行的基础表达式是：2N+10, 那么最坏的情况就是N取无穷大，那么2倍的无穷大还是无穷大，而+10简直等于没有，那么影响整个表达式的变量直邮N一个了，所以是O（N）

---

2.

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

 答案：O(M+N)

一般情况下都会用N做未知数，但是M+N都是不知道大小（未知数），M和N都需要留下

如果有说明N远大于M，则为O(N)；如果M远大于N，则为O(M)；如果N和M一样大，O(N)或者O(M)都可以

---

3.

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

答案：O（1）

所有的常数项都视作1。

---

4.

// 计算strchr的时间复杂度？
const char* strchr(const char* str, int character);

strcr的作用是在一串字符串内寻找一个指定字符。

答案：O（N）

我们取最坏的情况，也就是要找的字符在最后一个，整个计算的基本操作执行次数取决于整个字符串的长度。

---

5.

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

 答案：O(N^2)

我们知道冒泡循环的执行次数其实是一个等差数列：(N*(N-1)/2),那么根据我们求取最坏情况的思想以及大O渐进求法，求得的就是N^2.

6.：

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	// [begin, end]：begin和end是左闭右闭区间，因此有=号
	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)

由于每次进行折半查找，我们取最坏情况来计算，也就是最后一次折半才找到，那么假如数组长度为8，那么最坏查找3次，同理长度为N，最坏查找就是logN

因为在文本中不好写对数，于是我们简写成logN在算法分析中表示是底数为2，对数为N。有些地方会写成lgN（数学中lgN是以10为底，这种写法有歧义，最好写成logN）

---

7.

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

答案：O(N)

每次递归执行一次，执行次数取最坏情况也就是N的大小。

---

 8.

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

 答案： O(2^N)

我们其实很容易看的出来，斐波那契运算操作的次数其实是一个等比数列。

---

综上所述，我们大概了解了大多数时间复杂度的计算方法，先计算执行次数，然后根据求取原理进行化简，化简时应带入极限思想，也就是最坏情况。

 通常主要有以下几种表达式来描述时间复杂度：

• O(1)：      常量时间
• O(n)：      线性时间
• O(log n)：对数时间
• O(n^2)：  二次方时间
• O(2^n)：  指数时间
• O(n!)：     阶乘时间

为了更直观的理解这些函数表达式，函数曲线如上。

空间复杂度：

在这里，空间占用的是否少的感念并不是一段代码的复杂程度，比如我们用递归去求斐波那契数列的时候写的代码：

long long Fib (int N)
{
    if (N<3)
    return 1;
 
    return Fib (N-1) + Fib (N-2);
}

十分简洁是吧？但是我们都知道这段程序消耗的栈帧空间是非常巨大的。

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使用大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;
	}
}

答案：O(1)

使用了常数个额外空间，所以空间复杂度为 O(1)，虽然其中也有创建其他的栈帧，但是在使用完毕之后都直接归还了，重复利用的空间只有常数个，也没有使用额外的空间所以是O（1）

---

 2.

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

答案： O(N)

 实例2动态开辟了N个空间，空间复杂度为 O(N)

开辟额外的空间数量为N，最坏情况也只能达到N的级别所以答案是O(N)

---

3.

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

 答案为：O(N)

实例3递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)同上的道理，开辟的额外空间数量为N。

复杂度的oj练习：

消失的数字：

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

 

int missingNumber(int* nums, int numsSize){
 
    int total1 = 0;
    int total2 = 0;
    for(int i = 0;i<numsSize+1;i++)
    {
        total1 += i;
    }
 
    for(int i = 0;i<numsSize;i++)
    {
        total2 += nums[i];
    }
 
    return total1 - total2;
}

这题不算困难，只需要获取整个数组为缺失的所有数字之和减去现缺失数组之和，得到的差就是缺失的数字。

旋转数组：
https://leetcode-cn.com/problems/rotate-array/

 我们最容易想到的方法是额外创建一个数组，找到旋转之后的1的位置，向新数组存放，然后再找到之后的数字，最后将新数组覆盖。

void rotate(int* nums, int numsSize, int k) {
    int newArr[numsSize];
    for (int i = 0; i < numsSize; ++i) {
        newArr[(i + k) % numsSize] = nums[i];
    }
    for (int i = 0; i < numsSize; ++i) {
        nums[i] = newArr[i];
    }
 
    return nums;
}

其中，取余的操作可以巧妙的让数字直接返回初始处。

不过这题为了优解，还有三步辗转法

void reverse(int*nums,int left,int right)
{
    while(left<right)
    {
        int tmp=nums[left];
        nums[left]=nums[right];
        nums[right]=tmp;
        --right;
        ++left;
    }
}
 
 
void rotate(int* nums, int numsSize, int k){
    k%=numsSize;    
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-k-1);
    reverse(nums,0,numsSize-1);
 
}

 比较难想得到，不过也可以扩大我们思维的广度。

至此，记述结束!感谢阅读！希望对你有些帮助！