[数据结构]1.时间复杂度和空间复杂度

1. 算法复杂度

衡量一个算法的好坏，一般是从时间空间两个维度来衡量，即时间复杂度和空间复杂度。
时间复杂度衡量算法的运行快慢，空间复杂度衡量算法运行所需要的额外空间。

2. 时间复杂度

算法的时间复杂度是一个函数，定量描述了该算法的运行时间。
算法花费的时间与其中语句的执行次数成正比，算法中的基本操作的执行次数，为算法的时间复杂度。

2.1 执行次数

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

Func1 执行的基本操作次数 ：F(N)=N^2+2*N+10
实际计算时间复杂度时，不一定要计算精确，只需要大概执行次数，使用大O的渐进表示法O(N^2)

2.2 大O渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶方法：

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

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

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

2.3 常见时间复杂度计算

eg1

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

F(N)=2N+10 --> O(N)

eg2

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 --> O(M+N)

eg3

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

F(N)=100 --> O(1)

eg4

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

strchr函数用于在给定字符串str中查找字符character首次出现的位置。如果找到，返回指向该字符的指针；如果未找到，返回NULL 。
最好情况：1；最坏情况：O(N)

eg5

// 计算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(N)；最坏情况：O(N^2)

eg6

// 计算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);
		//((end - begin) >> 1) 相当于 (end - begin) / 2
		//这样写可以避免 (begin + end) / 2 可能导致的溢出问题（当 begin 和 end 很大时）
		if (a[mid] < x)//如果中间位置的值 a[mid] 小于要查找的值 x，说明 x 在 mid 的右侧，所以将 begin 更新为 mid + 1
			begin = mid + 1;
		else if (a[mid] > x)//如果中间位置的值 a[mid] 大于要查找的值 x，说明 x 在 mid 的左侧，所以将 end 更新为 mid - 1
			end = mid - 1;
		else//如果 a[mid] 等于 x，说明找到了目标值，直接返回 mid，即目标值在数组中的下标
			return mid;
	}
	return -1;
}

eg7

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

对于输入为N时，函数会进行N次递归调用，每次递归调用除了递归自身外其他操作时间近似为常数，所以整体时间复杂度与输入规模N成线性关系，即O(N)。

eg8

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

每次递归调用都会产生两个新的递归调用，随着N的增大，计算量呈指数增长。
计算Fib(N)时，需要计算Fib(N - 1)和Fib(N - 2)，而计算Fib(N - 1)又需要计算Fib(N - 2)和Fib(N - 3)等等，存在大量的重复计算，导致计算量迅速膨胀。O(2^N)

eg9

消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
示例：

• 输入：[9,6,4,2,3,5,7,0,1]
• 输出：8

分析：

1. 先排序，再查找，n的下一个数字不是n+1，则n+1为缺失数字
   N*logN+N -->O(N*logN)
2. 异或 （同0异1）（a^ba=b）
   O(2N)–>O(N)

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

3. 用0~N的等差数列公式计算数组之和，减数组中的值
   O(N)

int missingNumber(int* nums, int numsSize) {
    int x = (1 + numsSize) * numsSize / 2;
    for (size_t i = 0; i < numsSize; ++i) {
        x -= nums[i];
    }
    return x;
}

3. 空间复杂度

空间复杂度是一个数学表达式，对算法在运行过程中临时占用额外存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间，算的是变量的个数，使用大O渐进表示法。
注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

eg1

// 计算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) ，因为除了输入数组本身外，额外使用的空间不随输入规模增长

eg2

// 计算Fibonacci的空间复杂度
// 返回斐波那契数列的前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)，因为它分配了一个大小为n + 1的数组来存储斐波那契数列的前n项，空间使用量与输入的n成正比。

eg3

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

每次递归调用都会在栈上创建一个新的栈帧。在最坏情况下，会递归 N 次，所以空间复杂度是 O(N)。因为递归调用栈的深度最大为 N，需要 O(N) 的栈空间来存储每一层递归调用的状态。

eg4

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

O(N)，深入建立栈帧，函数结束销毁栈帧，再建立栈帧还是在该空间建立，所以一共建立N个栈帧，Fib(N-1) + Fib(N-2);使用的是同一块栈帧

4. 常见复杂度对比

5. 复杂度练习

eg1

轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

1. 暴力求解，旋转k次
   时间复杂度：k=n-1,kn–> O(N^2)
   空间复杂度：O(1)
2. 三段逆置
   4 3 2 1 5 6 7 前n-k逆置
   4 3 2 1 7 6 5 后k 逆置
   5 6 7 1 2 3 4 整体逆置
   时间复杂度：O(N)
   空间复杂度：O(1)

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

3. 空间换时间
   将前后拷贝至tmp，再拷贝到a
   a=[1 2 3 4 5 6 7]
   tmp=[5 6 7 1 2 3 4]
   时间复杂度：O(N)
   空间复杂度：O(N)

void rotate(int* nums, int numsSize, int k) {
    if (k > numsSize)
        k %= numsSize;
    int* tmp = (int*)malloc(sizeof(int) * numsSize);
    memcpy(tmp + k, nums, sizeof(int) * (numsSize - k));
    memcpy(tmp, nums + numsSize - k, sizeof(int) * (k));
    memcpy(nums, tmp, sizeof(int) * (numsSize));
    free(tmp);
}