具体关于：时间复杂度和空间复杂度的概念讲解和规则，请老铁们移步我的上一篇文章！# 数据结构之时间复杂度和空间复杂度
时间复杂度经典例题分析
规则
例题 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)
例题 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 = 10242^20 约等于100W 实际大于100W2^30 约等于10亿
复制代码
问：在 14 亿有序的人口中查找一个人，最多查找多少次
递归算法如何计算时间复杂度：
递归次数*每次递归调用的次数
例题 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)
==递归中：栈帧的消耗看递归的深度==
常见复杂度对比
时间复杂度和空间复杂度例题就讲解到这里啦，如果对你有所帮助的话，欢迎三连支持一下博主！欢迎各位大佬批评指正！
评论