公司网站建设工作通知,wordpress 媒体库 显示,免费模板简历网站,烟台做网站谁家好全文目录引言如何衡量一个算法的好坏时间复杂度时间复杂度的定义时间复杂度的大O表示法实例test1test2test3test4test5总结引言
如何衡量一个算法的好坏
我们在写算法的时候#xff0c;对于实现同样的作用的不同算法#xff0c;我们如何判断这个算法的好坏呢#xff1f;
…
全文目录引言如何衡量一个算法的好坏时间复杂度时间复杂度的定义时间复杂度的大O表示法实例test1test2test3test4test5总结引言
如何衡量一个算法的好坏
我们在写算法的时候对于实现同样的作用的不同算法我们如何判断这个算法的好坏呢
我们很容易的想到可以通过这个算法计算某用例的时间与所额外占用的空间来判断。 但是对于不同的计算机而言数据读取与处理的速度与方式是可以有很大的差别的。所以单纯的根据算法某次运行的时间与空间来判断算法的效率高低是没有说服力的。
所以我们使用时间复杂度与空间复杂度这两个标准来衡量算法的效率的高低。 在本篇文章中将介绍时间复杂度
时间复杂度
时间复杂度的定义
在计算机科学中时间复杂度是一个函数它定量的描述了一个算法运行的时间。
前面提到要实际的测出算法的运行时间是很麻烦的有很多的不确定变量。而算法运行的时间往往与其中语句的执行次数成正比所以算法中基本语句的执行次数为算法的时间复杂度。
时间复杂度的函数就是基本语句数量与相关变量之间的数学关系式。
例如
int fun(int n)
{int i 0;int j 0;int count 0;for (i 0; i n; i){for (j 0; j n; j){count;}}for (i 0; i 2 * n; i){count;}int m 10;while (m--){count;}return count;
}在这段代码中
基本语句的数量与变量n与变量m有关而m的值是恒定的。 所以我们可以得到这个函数的时间复杂度的数学表达式为 n^22*n10。
虽然对于上面的代码而言找到精确的数学表达式来表示时间复杂度是很容易的但是对于一些比较复杂的算法而言想要找到精确的函数是很困难的。所以我们使用大O表示法来表示时间复杂度的大概值。
时间复杂度的大O表示法
大O符号是用于描述函数渐进行为的数学符号。
我们在使用大O表示法表示时间复杂度时去掉对结果影响不大的项即可。 大O表示法的转换规则如下
1、用常数1表示算法中的所有加法常数 2、在修改后的数学表达式中只保留最高项 3、如果最高项存在且不是1则去掉该最高项的系数。 得到的结果就是大O阶。
对于上面的fun函数 我们已经得到了该数学表达式n^22*n10。 首先将常数10改为1再将最高项保留即n^2这一项的系数为1。 所以大O阶就为 O(n^2)。
另外某些算法在运行时对于不同的用例可能会有不同的情况。这时我们采取最慢的情况来计算时间复杂度。
实例
在实际用大O阶表示时间复杂度的时候我们其实并不用通过精确的数学表达式来推出只需要将该算法基本语句的量级表示出来即可。例如对数级log n、正比例级n、次方级n^2、指数级2^n等。这些量级都是可以用函数图像表示出来的
例如上面的fun函数的量级就是n^2级的。
而确认量级的最佳途径往往是画图接下来将通过几个栗子来说明
test1
void test1(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}在这段代码中 显然算法的基本操作的数量与k相关。
k的值从0开始随着算法的执行递增1到100终止。所以我们可以画出它大概的图像 根据大O阶表示法这个算法的时间复杂度就是O(1)。
test2
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^n次
test3
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;
}这段代码就是经典的二分查找算法
对于二分查找是从n开始每次范围减少一半知道剩余1个元素。 所以1乘以2的查找次数次方就是n即需要执行log n次。我们就可以画出关系图 需要注意的是由于书写较麻烦对于log以2为底n的对数所以可以用log n表示。
test4
long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}这是一个函数递归的算法
将N-1的值再传给函数本身直到N为0时终止递归。 很明显该算法每次递归N递减1所以执行N次基本语句 test5
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}这是一个递归实现斐波那契数列的算法
对于该算法每次递归都会引起两次递归即两次基本语句N-1与N-2。直到参数3终止。 我们可以先画出这个算法的程序图 不难发现基本语句的量级是指数增长的所以该算法的时间复杂度为O(2^n)
总结
到此关于时间复杂度的知识就介绍完了。 在下一篇文章中将详细介绍空间复杂度的相关知识希望持续关注哦
如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题欢迎大家在评论区提出
如果本文对你有帮助希望一键三连哦
希望与大家共同进步哦
