【数据结构与算法篇】之时间复杂度与空间复杂度
【数据结构与算法篇】之时间复杂度与空间复杂度
- 一、时间复杂度
-
- 1.1时间复杂度的定义
- 1.2 常见的时间复杂度的计算
-
- 1.2.1 常数时间复杂度（
O
(
1
)
)
O(1))
O(1))
- 1.2.2 线性时间复杂度（
O
(
N
)
O(N)
O(N)）
- 1.2.3 对数时间复杂度（
O
(
l
o
g
N
)
O(log N)
O(logN)）
- 1.2.4 平方时间复杂度（
O
(
N
2
)
O(N^2)
O(N2)
- 1.2.1 常数时间复杂度（
- 1.3 常见的函数的时间复杂度
- 二、空间复杂度
- 2.1 空间复杂度的定义
- 2.2 常见的空间复杂度的计算
- 2.2.1 常数空间复杂度
(
O
(
1
)
)
(O(1))
(O(1))
- 2.2.2 线性空间复杂度
(
O
(
n
)
)
(O(n))
(O(n))
- 2.2.3 平方空间复杂度
(
O
(
n
2
)
)
(O(n^2))
(O(n2))
- 2.2.4 对数空间复杂度
(
O
(
l
o
g
n
)
)
(O(logn))
(O(logn))
- 2.2.1 常数空间复杂度
❤️博客主页： 小镇敲码人
🍏 欢迎关注：👍点赞 👂🏽留言 😍收藏
🌞友友们暑假快乐，好久不见呀！！！💖💖💖
🍉 有人曾经问过我这样一个问题，“人终其一身，执着追求的东西究竟是什么？”我是这样回答的，”我们终其一生都在寻找着那个和我们灵魂极其契合的人，可最后才发现，那个人只有也只能是自己，学会在无聊时消遣自己是非常重要的“，所以无论目前屏幕上的你深处怎样的绝境之中，请不要放弃自己，好好的爱自己就是度过绝境的最佳武器！！！😸😸😸
一、时间复杂度
1.1时间复杂度的定义
在计算机与科学中，算法的时间复杂度（time complexity）是一个函数，它定性的描述算法的运行时间，表示一个程序来回执行的次数，但不定量。这个函数的自变量是算法输入值的字符串的长度，即
N
N
N。时间复杂度常用大O符号表述，只包括那个幂次最高的项数。使用这种方式时，时间复杂度可被称为是渐近的，也就是
lim
N
→
∞
O
(
N
)
\lim\limits_{N\rarr\infin}O(N)
N→∞limO(N)时的情况。例如，如果一个算法对于任何大小为
N
N
N的输入，它至多需要 5
N
3
N^3
N3 +
3
N
3N
3N 的时间运行完毕，那么它的渐近时间复杂度是
O
(
N
3
)
O(N^3)
O(N3)。
- 注意：时间复杂度不计算时间，只计算程序的执行次数。
常见的时间复杂度包括：
- 常数时间复杂度（
O
(
1
)
)
O(1))
O(1))：算法的执行时间与输入规模无关，常数级别的执行时间。
- 线性时间复杂度（
O
(
N
)
O(N)
O(N)）：算法的执行时间与输入规模线性相关，随着输入规模的增加而线性增长。
- 对数时间复杂度（
O
(
l
o
g
N
)
O(log N)
O(logN)）：算法的执行时间与输入规模的对数关系，通常是二分查找等算法的时间复杂度。
- 平方时间复杂度（
O
(
N
2
)
O(N^2)
O(N2)）：算法的执行时间与输入规模的平方相关，通常是嵌套循环等算法的时间复杂度。
- 线性对数时间复杂度
(
O
(
N
∗
l
o
g
N
)
)
(O(N*log N))
(O(N∗logN)) ：它表示随着输入规模 N 的增加，算法的执行时间以 N 乘以 log N 的速度增长,线性对数时间复杂度常常出现在一些高效的排序算法（如快速排序和归并排序）以及一些分治算法中。
注意：嵌套循环的算法时间复杂度不一定是
O
(
N
2
)
O(N^2)
O(N2)。
通过分析算法的时间复杂度，我们可以更好地理解算法的性能特点，并进行算法的选择和优化。
1.2 常见的时间复杂度的计算
1.2.1 常数时间复杂度（
O
(
1
)
)
O(1))
O(1))
int main() { int a = 0; a += 1; printf("%d",&a); return 0; }这段代码执行了四次操作。我们逐行分析代码的执行过程：
1.int a = 0;：这行代码初始化了整数变量a，将其赋值为 0。
2. a += 1;：这行代码将变量 a的值增加 1，现在 a 的值为 1。
3.printf(“%d”, &a);：这行代码使用 printf 函数打印变量 a 的值的内存地址，格式化输出为十进制整数。
4. return 0;：在 main 函数的结尾，使用 return 语句将返回值设为 0。
因此，代码执行了四次操作。
- 若对于一个算法
T
(
n
)
T(n)
T(n)的上界与输入大小无关，则称其具有常数时间，记作O(1)时间,故而这个算法的时间复杂度为
O
(
1
)
O(1)
O(1)。
1.2.2 线性时间复杂度（
O
(
N
)
O(N)
O(N)）
int main(){ int n = 0; scanf("%d",&n); int sum = 1; for(int i = 1;i < n;;i++) sum *= i; printf("%d",sum); return 0;}这段代码的执行过程如下：
- int n = 0;：这行代码声明了一个整数变量 n，并将其初始化为 0。
- scanf(“%d”,&n);：这行代码使用 scanf 函数从标准输入中读取一个整数，并将其赋值给变量 n。
- int sum = 1;：这行代码声明了一个整数变量 sum，并将其初始化为 1。
- for(int i = 1;i < n;i++)：这行代码开始一个 for 循环，循环变量 i 的初始值为 1，循环条件为 i < n。
- sum *= i;：这行代码将变量 sum 与变量 i 相乘，并将结果赋值给 sum。
- printf(“%d”,sum);：这行代码使用 printf 函数打印变量 sum 的值。
- return 0;：在 main 函数的结尾，使用 return 语句将返回值设为 0。
- 在for循环中，变量 i 的初始值为 1，每次循环 i 的值递增 1，直到达到 n 的值。因此，for 循环的执行次数为 n – 1。在循环中，执行了一次乘法操作 sum *= i，共执行了 n – 1 次。
- 故而程序的执行次数为：
T
（
N
）
=
5
+
2
∗
(
N
−
1
)
=
2
N
+
3
,
T（N）=5+2*(N-1)=2N+3,
T（N）=5+2∗(N−1)=2N+3,
lim
N
→
∞
T
(
N
)
=
O
(
N
)
\lim\limits_{N\rarr\infin}T(N)=O(N)
N→∞limT(N)=O(N)。
1.2.3 对数时间复杂度（
O
(
l
o
g
N
)
O(log N)
O(logN)）
#include void logarithmicAlgorithm(int n) { int i = 1; while (i < n) { printf("%d\n", i); i *= 2; // 对数时间复杂度的关键步骤 }}int main() { int n = 16; logarithmicAlgorithm(n); return 0;}这段代码的执行过程如下：
- 在 main函数中，声明一个整数变量 n 并赋值为 16。
- 调用logarithmicAlgorithm()函数，并将变量 n 作为参数传递给该函数。
- 进入logarithmicAlgorithm函数。
- 在logarithmicAlgorithm 函数中，声明一个整数变量 i 并赋值为 1。
- 进入 while 循环，检查条件 i < n 是否满足。由于此时 i 的初始值为 1，且 1 小于 16，条件成立，进入循环体。
- 在循环体内，使用printf 函数打印变量 i 的值。
- 执行i *= 2，将 i 的值乘以 2。
- 回到循环的开头，再次检查条件 i < n。如果条件仍然成立，继续执行循环体；如果条件不成立，跳出循环。
- 当 i 的值达到或超过 n（即 16）时，条件 i < n 不再满足，跳出循环。
- 退出logarithmicAlgorithm函数。
- 回到 main函数，继续执行后续的代码。执行return 0; 语句，结束程序。
- 设while循环的判断执行次数为x，
2
=
N
,
⇒
2
x
−
1
=
l
o
g
2
N
+
1
2 = N,\rArr 2^{x-1} = log_2N+1
2=N,⇒2x−1=log2N+1
while循环内的执行次数为
2
∗
l
o
g
2
N
2*log_2N
2∗log2N
- 故而程序的执行次数为：
T
（
N
）
=
7
+
3
∗
l
o
g
2
N
,
T（N）= 7+3 * log_2N,
T（N）=7+3∗log2N,
lim
N
→
∞
T
(
N
)
=
O
(
l
o
g
N
)
\lim\limits_{N\rarr\infin}T(N)=O(logN)
N→∞limT(N)=O(logN)。
1.2.4 平方时间复杂度（
O
(
N
2
)
O(N^2)
O(N2)
#include void quadraticAlgorithm(int n) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { printf("(%d, %d)\n", i, j); } }}int main() { int n = 3; quadraticAlgorithm(n); return 0;}这段代码的执行过程如下：
- 在main函数中声明一个整数变量n，并赋值为3。
- 调用quadraticAlgorithm()函数，并把变量n作为形参传递给函数。
- 进入函数quadraticAlgorithm()。
- 外部for循环的判断执行次数为n+1，外部循环循环一次内部for循环判断的执行次数为n+1，printf语句的执行次数为n。
故而外部for循环的执行次数就为n+1，内部for循环的总执行次数就为n*（n+1），内部for循环的printf语句的总执行次数为
n
2
n^2
n2
- 退出函数quadraticAlgorithm()。
- 继续执行main函数中的return 0;语句，结束程序。
- 故程序的执行次数为：
T
(
N
)
=
1
+
1
+
1
+
(
N
+
1
)
+
N
∗
(
N
+
1
)
+
N
∗
N
+
1
+
1
=
2
N
2
+
2
N
+
6
,
T(N) =1+1+1+(N+1)+N*(N+1)+N*N+1+1=2N^2+2N+6,
T(N)=1+1+1+(N+1)+N∗(N+1)+N∗N+1+1=2N2+2N+6,
lim
N
→
∞
T
(
N
)
=
O
(
N
2
)
\lim\limits_{N\rarr\infin}T(N)=O(N^2)
N→∞limT(N)=O(N2)
1.3 常见的函数的时间复杂度
以下图片整理了一些常用的时间复杂度类。表中，
p
o
l
y
(
x
)
=
x
O
(
1
)
poly(x) = xO(1)
poly(x)=xO(1)，也就是 x 的多项式。也可以访问网页版点击此处跳转
二、空间复杂度
2.1 空间复杂度的定义
在计算机科学中，一个算法或程序的空间复杂度定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应计算问题的输入值的长度的函数，它表示一个算法完全执行所需要的存储空间大小。和时间复杂度类似，空间复杂度通常也使用大O记号来渐进地表示。例如：
O
(
n
)
、
O
(
n
α
)
、
O
(
n
∗
l
o
g
n
)
、
O
(
2
n
)
O(n)、{\displaystyle O(n^{\alpha })}、O(n*logn)、O(2^n)
O(n)、O(nα)、O(n∗logn)、O(2n)。
空间复杂度用于评估算法在执行过程中所需的额外空间或内存的量级或增长趋势。它主要关注算法在运行过程中所使用的额外存储空间，包括算法使用的数据结构、临时变量、递归调用等。
- 注意：空间复杂度不计算空间，只计算变量的个数
常见的空间复杂度包括：
- 常数空间复杂度
(
O
(
1
)
)
(O(1))
(O(1))：算法使用固定的额外空间，不随输入的增加而变化。
- 线性空间复杂度
(
O
(
n
)
)
(O(n))
(O(n))：算法使用的额外空间与输入规模成线性关系。
- 平方空间复杂度
(
O
(
n
2
)
)
(O(n^2))
(O(n2))：算法使用的额外空间与输入规模成平方关系。
- 对数空间复杂度
(
O
(
l
o
g
n
)
)
(O(logn))
(O(logn))：算法使用的额外空间与输入规模成对数关系。
2.2 常见的空间复杂度的计算
- 就是去算变量和函数调用开辟的栈帧的个数之和
2.2.1 常数空间复杂度
(
O
(
1
)
)
(O(1))
(O(1))
void printHello() { printf("Hello, world!\n");}- 函数调用一次，开辟一个栈帧，空间复杂度为
O
(
1
)
O(1)
O(1)。
2.2.2 线性空间复杂度
(
O
(
n
)
)
(O(n))
(O(n))
void printNumbers(int n) { int *arr =(int*)malloc(n * sizeof(int)); // 执行其他操作... free(arr);}- 开辟了一个动态数组，变量的个数与
n
n
n成正比，取极限，和时间复杂度一样，常数可以忽略，空间复杂度为
O
(
n
)
O(n)
O(n)。
2.2.3 平方空间复杂度
(
O
(
n
2
)
)
(O(n^2))
(O(n2))
void printPairs(int n) { int **matrix = (int**)malloc(n * sizeof(int *)); for (int i = 0; i < n; i++) { matrix[i] = (int*)malloc(n * sizeof(int)); } // 执行其他操作... for (int i = 0; i < n; i++) { free(matrix[i]); } free(matrix);}- 开辟了一个二维的动态数组，变量的个数与
n
2
n^2
n2成正比，取极限，忽略常数，空间复杂度为
O
(
n
2
)
O(n^2)
O(n2)。
2.2.4 对数空间复杂度
(
O
(
l
o
g
n
)
)
(O(logn))
(O(logn))
// 递归二分查找函数int binarySearch(int arr[], int low, int high, int target) { if (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { return binarySearch(arr, mid + 1, high, target); } else { return binarySearch(arr, low, mid - 1, target); } } return -1; // 如果找不到目标元素，返回-1}数组是提前排好序的递增数组，假设同时存在的栈帧最多为x个,因为只有找不到或者找到了target函数才会返回，此时区间长度要么是1，要么没找到不构成区间了，函数调用产生的栈帧才会开始销毁，有
2
x
=
n
→
x
=
l
o
g
2
n
2^x=n\to x=log_2n
2x=n→x=log2n,也就是最多开辟了
l
o
g
2
n
log_2n
log2n个栈帧。
- 故取极限,空间复杂度
T
(
N
)
为
T(N)为
T(N)为
lim
N
→
∞
T
(
N
)
=
O
(
l
o
g
N
)
\lim\limits_{N\rarr\infin}T(N)=O(logN)
N→∞limT(N)=O(logN)。
本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/732e51ad49.html
相关推荐
-
Alpha-Beta 剪枝
Minimax 算法 定义 Minimax$ 算法又叫极小化极大算法，是一种找出失败的最大可能性中的最小值的算法。1 在局面确定的双人对弈里，常进行对抗搜索，构建一棵每个节点都为一…
-
【SM3哈希算法】算法原理
【SM3哈希算法】算法原理 参考： 文章目录 【SM3哈希算法】算法原理 一、算法简介 二、基本原理 三、具体流程 1、填充 2、分组 3、迭代压缩 C语言实现 一、算法简介 SM…
-
c—冒泡排序模拟qsort
一、冒泡排序 二、冒泡排序优化排各种类型数据 文章目录 一、冒泡排序 二、冒泡排序优化排各种类型数据 冒泡排序 冒泡排序原理：两两相邻元素进行比较 初级版 void bulle_s…
-
『新星计划 • 数据结构与算法』数据结构学习指南以及在校招中的重要性
文章目录 💐文章导读 💐导师自我介绍 💐数据结构与算法的重要性 🔓在岗位招聘中 🔓在校招笔试中 &#…
-
YOLOV5通道剪枝【附代码】
之前的博客中已经实现了YOLOv4、YOLOR、YOLOX的剪枝，经过了几天的辛勤努力，终于实现了YOLOv5的剪枝。相关链接如下： YOLOv4剪枝(剪枝相关细节理论这里有写)：…
-
「优选算法刷题」:在排序数组中查找元素的第一个和最后个位置
一、题目 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 …
-
leetcode刷题(1)
各位朋友们，大家好，从今天开始我将陆续为大家更新我自己每天的leedcode刷题，我将会为大家说明每一步的来由，保证你一天新学会几道题目。各位朋友可以跟着博主每天刷几道题，相信两个…
-
【数据结构–八大排序】之堆排序
💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 …
-
最详细的signal 通信协议讲解，双棘轮复杂加密
目录 了解signal的意思 起源： 涉及算法： signal技术优势： 使用signal的热门产品 Signal protocol 为了快速入门，先来了解一下signal pro…
-
深度图与RGB彩色图的对准（内附Python代码）
在使用RealSense深度相机前，必须把深度相机和RGB相机对准了使用。。。不然会导致采集到的图像不对齐（如下图所示）： 左边是RGB图像，右边是深度图像…
