成都网站建设企业,电子商务网站建设与管理期末考试,网站备备份教程,唐山公司做网站【数据结构与算法篇】之时间复杂度与空间复杂度 一、时间复杂度1.1时间复杂度的定义1.2 常见的时间复杂度的计算1.2.1 常数时间复杂度#xff08; O ( 1 ) ) O(1)) O(1))1.2.2 线性时间复杂度#xff08; O ( N ) O(N) O(N)#xff09;1.2.3 对数时间复杂度#xff08; O (… 【数据结构与算法篇】之时间复杂度与空间复杂度 一、时间复杂度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.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)) ❤️博客主页 小镇敲码人 欢迎关注点赞 留言 收藏 友友们暑假快乐好久不见呀 有人曾经问过我这样一个问题“人终其一身执着追求的东西究竟是什么”我是这样回答的”我们终其一生都在寻找着那个和我们灵魂极其契合的人可最后才发现那个人只有也只能是自己学会在无聊时消遣自己是非常重要的“所以无论目前屏幕上的你深处怎样的绝境之中请不要放弃自己好好的爱自己就是度过绝境的最佳武器 一、时间复杂度
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 , TN52*(N-1)2N3, TN52∗(N−1)2N3, 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 stdio.hvoid 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_2N1 2N,⇒2x−1log2N1 while循环内的执行次数为 2 ∗ l o g 2 N 2*log_2N 2∗log2N 故而程序的执行次数为 T N 7 3 ∗ l o g 2 N , TN 73 * log_2N, TN73∗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 stdio.hvoid 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循环的判断执行次数为n1外部循环循环一次内部for循环判断的执行次数为n1printf语句的执行次数为n。 故而外部for循环的执行次数就为n1内部for循环的总执行次数就为n*n1内部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) 111(N1)N*(N1)N*N112N^22N6, T(N)111(N1)N∗(N1)N∗N112N22N6, 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^xn\to xlog_2n 2xn→xlog2n,也就是最多开辟了 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)。
