关于学院网站建设的通知企业公司信息网

当前位置： 首页 > news >正文

关于学院网站建设的通知,企业公司信息网,免费域名注册地址,移动网站开发书籍有一堆数据需要排序#xff0c;A要使用快速排序#xff0c;B要使用堆排序#xff0c;A认为自己的代码更高效#xff0c;B也认为自己的代码更高效#xff0c;在这种情况下#xff0c;怎么来判断谁的代码更好一点呢#xff1f;这时候就有了时间复杂度和空间复杂度。 目录 …      有一堆数据需要排序A要使用快速排序B要使用堆排序A认为自己的代码更高效B也认为自己的代码更高效在这种情况下怎么来判断谁的代码更好一点呢这时候就有了时间复杂度和空间复杂度。 目录 一、算法效率 1.1 衡量算法好坏的关键 1.2 算法的复杂度 二、时间复杂度 2.1 时间复杂度的概念 2.2 大O的渐进表示法 2.3 常见的时间复杂度的计算案例 2.3.1 案例一 2.3.2 案例二 2.3.3 案例三 2.3.4 案例四 2.3.5 案例五 2.3.6 案例六 2.3.7 案例七 2.3.8 案例八 三、空间复杂度 3.1 空间复杂度的概念 3.2 常见的空间复杂度计算案例 3.2.1 案例一 3.2.2 案例二 3.2.3 案例三 3.2.4 案例四 四、常见的复杂度对比 五、复杂度的练习 5.1 消失的数字 5.2 旋转数组 一、算法效率 1.1 衡量算法好坏的关键 我们在之前探讨过斐波那契数列计算的两种方式即递归和循环这两种方式那种更好呢我们认为循环的方式更好使用递归去求斐波那契数列会有大量的重复计算那么显然循环的方式更好这两个代码可以直接分析出来但是对于其他一些不容易进行分析的算法我们用什么来作为算法好坏的标准呢这里就引入了算法复杂度的概念。 1.2 算法的复杂度 算法在编写成可执行程序后运行时需要耗费时间资源和空间资源。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。在下面的文章中我们会依次讲解时间复杂度和空间复杂度。 二、时间复杂度 2.1 时间复杂度的概念 时间复杂度不是算的算法所用的时间在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一 个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知 道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。 对于算法的时间复杂度我们不需要计算出精确的执行次数只需要对执行次数进行估算得到大致的量级在计算时间复杂度和空间复杂度的时候我们统一使用的是大O的渐进表示法。 2.2 大O的渐进表示法 在计算算法的复杂度的时候我们只需要得到大概次数所属的量级即忽落掉一些对结果影响不大的项在这里我们主要使用大O的渐进表示法。 大O符号Big O notation是用于描述函数渐进行为的数学符号。 推导大O阶方法 1.用常数1取代运行时间中的所有加法常数。 2.在修改后的运行次数函数中只保留最高阶项。 3.如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。 通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数。 对于有一些算法算法的时间复杂度存在最好、平均和最坏情况 1.最坏情况任意输入规模的最大运行次数(上界) 2.平均情况任意输入规模的期望运行次数 3.最好情况任意输入规模的最小运行次数(下界) 在实际中中一般情况关注的是算法的最坏运行情况。2.3 常见的时间复杂度的计算案例 2.3.1 案例一 // 计算Func2的时间复杂度 void Func2(int N) {int count 0;for (int k 0; k 2 * N ; k){count;}int M 10;while (M–){count;}printf(%d\n, count); } 在上面的概念中我们知道时间复杂度就是基本语句的执行次数在上述算法中有两个循环一个for循环执行2*N次一个while循环执行10次所以执行次数为2*N10次计算时间复杂度我们使用大O的渐进表示法忽略掉对整体影响不大的项所以在此算法中的时间复杂度为O(N)。 2.3.2 案例二 // 计算Func3的时间复杂度 void Func3(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); } 在上述算法中有两个for循环按照大O的渐进表示法上述算法的时间复杂度是O(MN)在此案例中并未对M和N的大小进行说明如果题目指明M远大于N那就说明N对最终结果影响不大可以忽略时间复杂度就是O(M);如果题目指明N远大于M那就说明M对最终结果影响不大可以忽略时间复杂度就是O(N);如果题目指明MN时间复杂度就是O(N)或者O(M)。 2.3.3 案例三 // 计算Func4的时间复杂度 void Func4(int N) {int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count); } 上述算法中基本语句的执行次数为100按照大O的渐进表示法时间复杂度为O(1)。 在这里如果有同学不理解常数阶的执行次数为什么一律用O(1)来表示实际上CPU是足够快的循环100000000次和循环100次对他而言时间都差不多所以他会认为是一个量级所以常数阶都用O(1)来表示。 2.3.4 案例四 // 计算strchr的时间复杂度 const char * strchr ( const char * str, int character ); 上述的strchr库函数的功能参数介绍如下图 strchr函数相当于 while(str) {if(str character)return str;elsestr; } 上述函数的时间复杂度我们需要分情况来看 //假设有一个字符串 a d c g e h e a x \0 //如果我们要在上述字符串中找a字符那么只需要找1次就可以找到时间复杂度为O(1)这个情况属于最好的情况。 //如果我们要在上述字符串中找x字符那么只需要找N假设一共有N个字符次就可以找到时间复杂度为O(N)这个情况属于最坏的情况。 对于时间复杂度我们一般关注的是最坏时间复杂度所以此算法的时间复杂度为O(N)。 2.3.5 案例五 // 计算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;} } 上述案例是冒泡排序冒泡排序的主题思想是两两相邻的元素进行比较对于冒泡排序一趟冒泡排序可以把一个数排到正确的位置上那么N个数就需要N-1趟冒泡排序在这里是冒泡排序的优化版本如果想要对冒泡排序了解的更加清晰可以看看我的《数组》那篇博文如果在进行循环的过程中数组已经是升序那么接下来的循环就不会再继续对于上述时间复杂度的计算我们主要通过思想来进行分析分为最好情况和最坏情况如下图 从上图我们就可以看出在最好情况下只需要进行一趟冒泡排序即N-1次的比较所以最好时间复杂度为O(1)在最坏情况下我们需要进行N-1趟冒泡排序每趟冒泡排序需要对两两相邻的数进行比较最坏情况下的执行次数为N-1N-2N-3……321N(N-1)/2按照大O的渐进表示法此算法的最坏时间复杂度是O(N^2)。 对于时间复杂度我们一般关注的是最坏时间复杂度所以此算法的时间复杂度为O(N^2)。 2.3.6 案例六 // 计算BinarySearch的时间复杂度 int BinarySearch(int a, int n, int x) {assert(a);int begin 0;int end n - 1;// [begin, end]begin和end是左闭右闭区间因此有号while (begin end){int mid begin ((end - begin) 1);if (a[mid] x)begin mid 1;else if (a[mid] x)end mid - 1;elsereturn mid;}return -1; } 二分查找是什么二分查找例如我们需要在arr {1,2,3,4,5,6,7,8,9,10}中找到7对应的下标此时我们先看中间的数即arr[4]此时数组中arr[4]对应的数字是5比7小我们从arr[5]到arr[9]范围内寻找再次找到arr[5]到arr[9]中间的数即arr[7],对应的数字是8比7大我们从arr[5]到arr[6]的范围找再找arr[5]到arr[6]中间的数即arr[5],arr[5]对应的数为6比7小此时再将arr[6]对应的数字与7比较相等二分查找的前提是有序。 上述算法是二分查找的算法这个算法也分为最好情况和最坏情况最好情况是进行一次二分查找就能够找到此时最好时间复杂度是O(1)。 接下来我们通过分析二分查找的算法来计算它的最坏时间复杂度 二分查找的时间复杂度为O(logN)。  2.3.7 案例七 // 计算阶乘递归Fac的时间复杂度 long long Fac(size_t N) {if(0 N)return 1;return Fac(N-1)N; } 上述算法涉及递归我们用图来解释 2.3.8 案例八 // 计算斐波那契递归Fib的时间复杂度 long long Fib(size_t N) {if(N 3)return 1;return Fib(N-1) Fib(N-2); } 此处补充斐波那契数列的知识斐波那契数列指的是这样一个数列0、1、1、2、3、5、8、13、21、34、55、89……满足从第3项起每一项都等于前两项之和我们可以使用递归来计算斐波那契数列。 使用递归求斐波那契数列的调用如下 需要注意的是在实际调用过程中如果我们要求Fib(5)图示如下 调用的模型类似于下方 三、空间复杂度 3.1 空间复杂度的概念 空间复杂度也是一个数字表达式是对一个算法在运行过程中临时占用存储空间大小的量度是这个算法额外开辟的空间空间复杂度不是程序占用了多少bytes的空间他计算的是变量的大小空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。 注意函数运行时所需要的栈空间存储参数、局部变量、一些寄存器信息等在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定。 3.2 常见的空间复杂度计算案例 3.2.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;} } 上述算法的空间复杂度是O(1)空间复杂度算的是由于算法额外需要开辟的空间即由于算法需要额外开辟的变量个数在上述算法中我们额外开辟了三个变量end、exchange、i按照大O的渐进表示法空间复杂度即为O(1)。 在这里许多人会有一个误区把函数的参数也算作额外开辟变量的个数这种想法显然不对函数的参数属于数据源即给一些数据按照算法对这些数据进行一定的处理最后得到想要结果这些数据不属于算法所需要的额外开辟的空间。 3.2.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; } 上述算法中额外开辟了n3个变量首先开辟了n1个long long类型的数据其次开辟了一个long long*类型的变量fibArray和int类型的变量i按照大O的渐进表示法空间复杂度为O(n)。 3.2.3 案例三 // 计算斐波那契递归Fib的空间复杂度 long long Fib(size_t N) {if(N 3)return 1;return Fib(N-1) Fib(N-2); } 求斐波那契递归的空间复杂度我们依然先看递归的调用图示 对于上述算法它的空间复杂度是O(N)主要是由于它的调用顺序   对于Fib(N),调用时先调用 Fib(N-1)然后调用Fib(N-2)一直到调用到Fib(2)然后返回Fib(2)的值把Fib(2)函数调用开辟的函数帧还给存储空间然后调用Fib(1)也就是说Fib(2)和Fib(1)是使用的同一块空间以此类推在此函数递归调用的过程中有一些调用复用同一块空间所以实际上该算法额外开辟的空间为N个即空间复杂度为O(N)。 此处主要还涉及了一些关于函数栈帧的创建与销毁的知识这部分知识大家可以从“我的资源”中找到或者私聊我要相关的笔记。 此处我们还可以通过求解Fib(5)来演示   3.2.4 案例四 // 计算阶乘递归Fac的空间复杂度 long long Fac(size_t N) {if (N 0)return 1;return Fac(N - 1) * N; } 上述的函数递归调用与案例三有所不同在本案例中函数调用层层嵌套此函数递归调用的方式类似下图: 对于上述函数的每次调用我们可以认为开辟了常数个变量需要进行N次函数调用所以上述算法的空间复杂度是O(N)。 四、常见的复杂度对比 一般算法常见的复杂度如下上图来源于百度如有侵权告知删除  五、复杂度的练习 5.1 消失的数字 oj链接https://leetcode-cn.com/problems/missing-number-lcci/
5.2 旋转数组 oj链接https://leetcode-cn.com/problems/rotate-array/
注上面两个题大家可以先做一下他们将在下一篇博客中具体分析。