数据结构-复杂度计算经典案例

---

具体关于：时间复杂度和空间复杂度的概念讲解和规则，请老铁们移步我的上一篇文章！# 数据结构之时间复杂度和空间复杂度

时间复杂度经典例题分析

规则

例题1：循环

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

共执行2*N+10次

常数可以忽略不计 O(2*N+10) ==>O(N)

时间复杂度为：O(N)

---

例题2：循环

void Func2(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);
}

共执行M+N次，由于M和N的大小未知，所以时间复杂度为：O(M+N)

• 情况1：M>>>N，则时间复杂度为：O(M)
• 情况2：N>>>M，则时间复杂度为：O(N)
• 情况3：M和N差不多大 则时间复杂度为：O(M)或者O(N)

---

例题3：循环

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

共执行100次，常数次->时间复杂度为0(1)

O(1)不是代表算法运行一次，而是常数次

---

例题4:strchr

strchr作用：在字符串中查找字符

返回字符第一次出现的位置，找不到返回NULL

---

模拟实现strchr

#include<stdio.h>
#include<assert.h>
char* my_strchr(const char* str, char c)
{
    assert(str);
    char* tmp = str;
    while (*tmp)
    {
        if (*tmp == c)
        {
            return tmp;
        }
        else
        {
            tmp++;
        }
    }
    return NULL;
}
int main()
{
    char* str = "Mangoa";
    printf("%s\n", my_strchr(str, 'a'));
    return 0;
}

---

回到正题：

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

最好情况：1次找到

平均情况：找了N/2次

最坏情况：找了N次

当一个算法随着输入不同，时间复杂度不同，时间复杂度做悲观预测，看最坏情况。

所以时间复杂度为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;
	}
}

每一趟冒泡排序可以让一个数在应该在的位置，每一趟可以排序好一个元素，有N个数，只需只需N-1次即可

第一趟：比较N-1个数

第二趟：比较N-2个数

…

第N-1趟：比较1个数

等差数列：F(N) = N*(N-1)/2

所以时间复杂度为：0(N^2)

---

例题6：二分查找(折半查找)

二分查找：每次减少1/2的查找范围，直到找到/找不到

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

---

关于二分查找

前提：有序

在1000个数中找1个数 ->最坏查找次数：10次

在100W个数中找1个数 ->最坏查找次数：20次

在10亿个数中找1个数 ->最坏查找次数：30次

---

2^10 = 1024
2^20 约等于100W 实际大于100W
2^30 约等于10亿

---

问：在14亿有序的人口中查找一个人，最多查找多少次

31次，  2^31 约等于20亿

---

递归算法如何计算时间复杂度：

递归次数*每次递归调用的次数

例题7：阶乘递归

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

例题8：斐波那契数列

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

虽然F(n-1)和F(n-2)都在F(N)的递归里面，但是他们不是同时调用的，是先调用完F(n-1)之后再调用F(n-2)

所以递归调用的次数为：1

---

空间复杂度经典例题分析

例题1：冒泡排序

// 计算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;
	}
}

额外开辟常量个空间：i和exchange和end

每次进入内循环时，exchange变量和i变量创建空间，出了内循环后，空间销毁。然后不断循环n次。**再一次创建是在同一个地方创建，本质上相当于没有销毁。**只占了那一个空间，所以时间复杂度是O(1)而不是O(N)，

---

例题2：斐波那契数列-循环版

// 计算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;
}

额外开辟了n+1个空间的数组，空间复杂度为：0(N)

时间复杂度也是0(N)，循环共执行了N-1次

---

例题3：求n的阶乘-递归

==递归中：栈帧的消耗看递归的深度==

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

==每次递归调用都开辟函数栈帧==，共开辟N个栈帧，每个栈帧使用了常数个空间。所以空间复杂度为：O(N)

---

经典名句：空间是可以重复利用的，但是时间是一去不复返的

---

例题4：斐波那契数列-递归版

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

最多创建N个栈帧，后序开辟的都不会比N多

所以空间复杂度为:O(N)

==递归中：栈帧的消耗看递归的深度==

---

常见复杂度对比

时间复杂度和空间复杂度例题就讲解到这里啦，如果对你有所帮助的话，欢迎三连支持一下博主！欢迎各位大佬批评指正！

---