个人网站备案备注范文,做学分网站,王占山教授,wordpress国内网站吗文章目录 引入算法 1、时间复杂度1.概念2.大O渐进表示法3.常见时间复杂度计算举例 2、空间复杂度1.概念2.常见空间复杂度计算举例 引入
算法
算法就是一段能将一个物体从初始状态转换到某个目标转态的一个有限长序列方法的统称
算法效率#xff1a;考虑一个方法是否好… 文章目录 引入算法 1、时间复杂度1.概念2.大O渐进表示法3.常见时间复杂度计算举例 2、空间复杂度1.概念2.常见空间复杂度计算举例 引入
算法
算法就是一段能将一个物体从初始状态转换到某个目标转态的一个有限长序列方法的统称
算法效率考虑一个方法是否好就要从它的效率上考虑能高质量(即高效)的完成目标的算法就是一个好的算法而对于算法效率要怎么来进行判定呢
与算法效率有关的因素有很多包括算法所需的时间、空间成本等因素在计算机相关中包括网络运行速度硬件等因素都会对效率产生影响而这些因素都是我们所无法掌控的所以我们在进行算法效率评定中大致以所需的时间和空间作为主要的衡量标志来对算法效率进行一个判定这就是时间复杂度与空间复杂度。
1、时间复杂度
1.概念
在计算机中算法的时间复杂度也有定量的函数其实也就是他将目标从初始状态转换为目标状态所需花费的时间。就从理论上来讲想要获取一个算法的时间复杂度那就必须将在计算机上运行然后测量所需的时间才能计算出它的时间复杂度。但在实际生活中这种方式较为难以实现所以我们将算法中基本操作的执行次数来作为它的时间复杂度。
我们就以下方的代码来进行一个举例:
//请计算Test1中count所执行的次数
void Test1(int N)
{int count 0;for (int i 0; i N; i){for (int j 0; j N; j){count;}}for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}在如上代码中count一共执行了N^2 2N 10次
实际上我们计算算法的时间复杂度时并不需要将准确的执行次数计算出来而是只需要渐进的表示。因为当你将量级拉大比如几十万、几百万次执行中几十、几百次的执行次数对于整体来说影响也不大。我们通常使用的方法是大O渐进表示法。
2.大O渐进表示法
1.表示方法O表达式中影响最大的哪一项 2.推荐大O表示法 1确定的常数次我们都使用O(1) 来表示原因只要是常数次它就不是未知数的影响无论基数多大它都不会变意味着效率不变 2ON 意味着随着N的变化运算时间变长 3对于有些会有最好情况、最坏情况、与平均情况这时候的时间复杂度是保守的估算取最坏结果 3.注意 1不是说一次循环就是On,两次循环就是on^2具体要通过程序区分析 2时间复杂度计算不能去数代码执行的次数要根据思想去计算时间复杂度然后看哪个更优再去实现
4.常见的时间复杂度O(N^2) , O(N) , O(logN) , O(1)
3.常见时间复杂度计算举例
void Test2(int N)
{int count 0;for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}void Test3(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);
}Test2就是刚刚我们所计算的那道题用大O表示法来进行表示它的时间复杂度是O(N^2)
Test3中基本操作执行了MN次有两个未知数M和N时间复杂度为 O(NM)
2、空间复杂度
1.概念
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。
在当今世界中由于电脑手机等的储存空间大大增加所以我们在实际处理问题中对与时间复杂度考虑式要优先于空间复杂度的。
2.常见空间复杂度计算举例
// 计算BubbleSort的空间复杂度
void Test4(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;}
}// 计算阶乘递归Fac的空间复杂度
long long Test5(size_t N)
{if (N 0)return 1;return Fac(N - 1) * N;
}Test4中使用了常数个额外空间所以空间复杂度为 O(1)
Test5中递归调用了N次开辟了N个栈帧每个栈帧使用了常数个空间。空间复杂度为O(N)
