wordpress html音乐,seo关键词优化工具,策划公司英文,做网站域名不备案会怎么样#x1f6a9;纸上得来终觉浅#xff0c; 绝知此事要躬行。 #x1f31f;主页#xff1a;June-Frost #x1f680;专栏#xff1a;数据结构 #x1f525;该文章主要了解算法的时间复杂度与空间复杂度等相关知识。 目录#xff1a; #x1f30f; 时间复杂度#x1f52d… 纸上得来终觉浅 绝知此事要躬行。 主页June-Frost 专栏数据结构 该文章主要了解算法的时间复杂度与空间复杂度等相关知识。 目录 时间复杂度 一些例子 空间复杂度❤️ 结语 时间复杂度和空间复杂度是计算机科学中用来评估算法效率的两个重要概念。它们分别描述了算法在执行时间和额外内存使用方面的需求帮助我们了解算法在处理输入数据时所需的资源。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。 时间复杂度 在计算机科学中算法的时间复杂度是一个函数用于度量算法执行时间的指标。因为一个算法所花费的时间与其中语句的执行次数成正比例所以可以认为在算法中的基本操作的执行次数为算法的时间复杂度。 计算时间复杂度时,其实并不一定要计算精确的执行次数,只需要大概执行次数即可。 ✨表示方式为大O的渐进表示法记作T(n) O(f(n))其中T(n)表示算法执行时间f(n)表示问题规模n的函数。具体来说当n趋近于无穷大时算法执行时间的增长趋势与f(n)的增长趋势相同的最高阶项即为该算法的时间复杂度。 ✨推导方式 用常数1取代运行时间中的所有加法常数。运行次数函数中只保留最高阶项。只关注数量级而忽略常数因子即去掉系数。 一些例子
①
void exampleAlgorithm(int N)
{for (int i 0; i N; i){for (int j 0; j N; j){printf(This is O(n^2) operation.\n);}}for (int k 0; k 2 * N; k){printf(This is O(n) operation.\n);}for (int M 5; M 0; M--){printf(This is O(1) operation.\n);}}这个例子的函数表达式为 F(N) N2 2*N 5随着N的不断增加N2 对最终结果具有决定性的作用所以N2就是它的量级运用大O的渐进表示法就可以表示为O(N2) 。
②
void exampleAlgorithm(int N)
{for (int k 0; k 2 * N; k){printf(This is O(n) operation.\n);}for (int M 5; M 0; M--){printf(This is O(1) operation.\n);}}如果没有了嵌套这个函数的表达式就变成了 F(N) 2*N 5这样随着N的增加有决定性效果的就是2 * N但是为了简化复杂度的表示并突出算法随输入数据规模增长的趋势又因为系数对于这种增长趋势的影响较小所以一般需要去除系数时间复杂度为O(N) 。
③
void exampleAlgorithm()
{for (int M 1000; M 0; M--){printf(This is O(1) operation.\n);}}如果只有常数阶那么就可以直接表示为O(1) 。
⚠注意 通过上面这些例子我们会发现大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数但是有些算法的时间复杂度存在最好、平均和最坏情况在实际中一般关注的是算法的最坏运行情况。 ④冒泡排序
void bubble_sort(int* arr, int sz)
{int i 0;for (i 0; i sz - 1; i){int flag 1; //标记int j 0;for (j 0; j sz - 1 - i; j){if (arr[j] arr[j 1]){flag 0;int temp 0;temp arr[j 1];arr[j 1] arr[j];arr[j] temp;}}if (flag 1)//如果等于1表示数组数据已经有序{break;}}
}对于冒泡排序最好的情况就是本身有序只需遍历比较一遍数组即可这时的时间复杂度为O(N)最坏的情况就是逆序排好第一个数据需要比较N-1次排好第二个数据需要比较N-2次…排好倒数第二个数据需要比较1次最后一个数据不需要比较将次数相加就是 [N*(N-1)] / 2量级为N2时间复杂度就是O(N2)最终的时间复杂度需要取最坏情况即O(N2)。
⑤二分查找
int BinarySearch(int* arr, int sz, int k)
{int left 0;int right sz - 1;while (left right){int mid (right left) / 2;if (arr[mid] k){left mid 1;//调整范围}else if (arr[mid] k){right mid - 1;//调整范围}else{return mid;}}return -1;
}最好的情况是第一次查找就找到了为O(1)。 最坏的情况为数据在边缘或者数组中没有要查找的数据: 一般将 log2N 简写为logN 所以时间复杂度为 O(logN)。
⑥ 阶乘
long long Factorial(size_t N)
{if (N 0)return 1;return Factorial(N - 1) * N;
}调用函数需要创建栈帧传入参数后会调用Factorial(N) ,再调用Factorial(N-1)不断调用直到调用到Factorial(0)共调用了N1次每次调用的时间复杂度为O(1)所以最终的时间复杂度为O(N) 。
⑦ 斐波那契数
long long Fibonacci(size_t N)
{if (N 2)return 1;return Fibonacci(N - 1) Fibonacci(N - 2);
}将 20 一直加到 2(n-2) ,算法的量级为2n虽然实际上右边的分支会缺少一部分但是不会影响到这个量级。 空间复杂度 空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度算的是变量的个数计算规则基本跟实践复杂度类似也使用大O渐进表示法。
⚠注意 函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 ① 冒泡排序 冒泡排序属于原地排序在排序过程中并没有使用额外的空间来帮助排序那些用来循环的变量可以看作常数阶所以冒泡排序的空间复杂度为O(1) 。
②阶乘
long long Factorial(size_t N)
{if (N 0)return 1;return Factorial(N - 1) * N;
}阶乘可以看作额外开辟了N个栈帧每个栈帧空间内部没有额外创建空间即每个栈帧空间为O(1)最终的空间复杂度为O(N) 。
③斐波那契数
long long Fibonacci(size_t N)
{if (N 2)return 1;return Fibonacci(N - 1) Fibonacci(N - 2);
}栈帧空间是可以复用的,所以通常用计算算法所占用的内存空间的最大值来评估算法的空间复杂度只需要知道在递归中会最大开辟多少栈帧空间就可以进行计算这个算法最多开辟栈帧数量的量级为N每个栈帧空间为O(1)所以最终的空间复杂度为O(N)。 ❤️ 结语 文章到这里就结束了如果对你有帮助你的点赞将会是我的最大动力如果大家有什么问题或者不同的见解欢迎大家的留言~
