html5制作网站首页,网站策划步骤,专业app开发制作团队,电子商务网站开发报告第一章、如何分析代码的执行效率和资源消耗 我们知道#xff0c;数据结构和算法解决的是“快”和“省”的问题#xff0c;也就是如何让代码运行得更快#xff0c;一级如何让代码更节省计算机的存储空间。因此#xff0c;执行效率是评价算法好坏的一个非常重要的指标。那么数据结构和算法解决的是“快”和“省”的问题也就是如何让代码运行得更快一级如何让代码更节省计算机的存储空间。因此执行效率是评价算法好坏的一个非常重要的指标。那么如何衡量算法的执行效率尼这里就要用到我们本节要讲的内容时间复杂度分析和空间复杂度分析。
一、复杂度分析的意义 我们把代码运行一遍通过监控和统计手段就能得到算法执行的时间和占用的内存大小为什么还要做时间复杂度分析空间复杂度分析呢这种“纸上谈兵”似的分析方法比实实在在地运行一遍代码得到的数据更准确吗 实际上这是两种不同的评估算法执行效率的方式。对于运行代码来统计复杂度的方法很多有关数据结构和算法的图书还给它起了一个名字事后统计法。这种统计方法看似可以给出非常精确的数值但是却有非常大的局限性。
1、测试结果受测试环境的影响很大 在测试环境中硬件的不同得到的测试结果会有很大的差异。例如我们用同样一段代码分别在安装了Intel Core i9处理器CPU和Intel Core i3处理器的计算机上运行显然代码在安装了Intel Core i9处理器的计算机上要比在安装了Intel Core i3处理器的计算机上的执行速度快得多。又如在某台机器上a代码执行的速度比b代码快当我们换到另外一台配置不同的机器上时可能会得到截然相反的运行结果。
2、测试结果受测试数据的影响很大 我们会在后续章节详细讲解排序算法这里用它进行举例说明。对同一种排序算法待排序数据的有序度不一样排序执行的时间会有很大的差别。在极端情况下如果数据已经是有序的那么有些排序算法不需要做任何操作执行排序的时间就会非常短。除此之外如果测试数据规模太小那么测试结果可能无法真实地反应算法的性能。例如对于小规模的数据排序插入排序反而比快速排序快 因此我们需要一种不依赖具体的测试环境和测试数据就可以粗略地估计算法执行效率的方法。这就是本节要介绍的时间复杂度分析和空间复杂度分析。
二、大O复杂度表示法 如何在不运行代码的情况下用“肉眼”分析代码后得到一段的执行时间尼下面用一段非常简单的代码来举例看一下如何估算代码的执行时间。求1~n的累加和的代码如下所示
public static int cumulativeSum(int n){int result 0;for (int i 1; i n; i){result i;}return result;
} 从在CPU上运行的角度来看这段代码的每一条语句执行类似的操作读数据--运算--写数据。尽管每一条语句对应的执行时间不一样但是这里只是粗略估计我们可以假设每条语句执行的时间一样为unit_time。在这个假设的基础上这段代码的总执行时间是多少尼 执行第26行代码分别需要1个unit_time的执行时间第34行代码循环运行了n遍需要 2n x unit_time的执行时间。因此这段代码的总执行时间为(2n 2) x unit_time的执行时间。通过上面的举例分析我们得到一个规律一段代码的总的执行时间为T(n)例子中的(2n 2) x unit_time与每一条语句的执行次数累加数例子中的2n 2成正比。 按照这个分析思路我们再来看另一段代码如下所示
public static int cal(int n){int sum 0;int i 1;int j;for (; i n; i){j 1;for (; j n; j){sum sum (i * j);}}return sum;
} 依旧假设每条语句的执行时间为unit_time那么这段代码的总的执行时间是多少尼 对于第23411行代码每行代码需要1个unit_time的执行时间。第56行代码循环执行了n遍需要2n x unit_time的执行时间。第78行代码循环执行了n²遍需要2n² x unit_time的执行时间。因此整段代码总的执行时间为T(n) (2n² 2n 4) x unit_time。尽管我们不知道unit_timede 具体值而且每一条语句执行时间unit_time可能都不尽相同但是通过这两段代码执行时间的推导过程可以得到一个非常重要的规律 一段代码的执行时间T(n)与每一条语句总的执行次数累加数成正比。 我们可以把这个规律总结成一个公式如下所示 T(n) O(f(n)) 下面具体解释一下公式。其中T(n)表示代码执行的总时间n表示数据规模f(n)表示每条语句执行次数的累加和这个值与n有关因此用f(n)这样一个表达式来表示公式中的O这个符号表示代码的执行时间T(n) 与 f(n)成正比。 套用这个大O表示法第一个例子中的T(n) (2n 2) x unit_time O(2n 2)第二个例子中的T(n) (2n² 2n 4) x unit_time O(2n² 2n 4)。实际上大O时间复杂度并不具体表示代码真正的执行时间而是表示代码执行时间随着数据规模增大的变化趋势因此也称为渐进时间复杂度asymptotic time complexity简称时间复杂度。 当n很大时读者可以把它想象成10000,100000公式中的低阶常量系数3部分并不控制增长趋势因此可以忽略。我们只需要记录一个最大量级。如果用大O表示法表示上面的两段代码的时间复杂度就可以记为T(n) O(n) 和 T(n) O(n²)。
补充知识 在数学中我们经常会听到关于“高阶”、“低阶”、“常量”和“系数”的术语。让我来解释一下 高阶High-order在多项式或函数中高阶项是指指数较高的项。例如在多项式 axnbxn−1cxn−2…axnbxn−1cxn−2… 中axnaxn 就是高阶项nn 是高阶项的指数。通常来说当 nn 越大该项的影响就越显著因此被称为“高阶”。 低阶Low-order与高阶相对应低阶项是指指数较低的项。在上面的多项式中bxn−1bxn−1 和 cxn−2cxn−2 就是低阶项。这些项的影响相对较小因为它们的指数较低。 常量Constant常量是没有包含任何变量的项它们是数学表达式中的固定值。在多项式 axnbxn−1cxn−2…daxnbxn−1cxn−2…d 中dd 就是常量项。 系数Coefficient系数是与变量相乘的数字或参数。在多项式 axnbxn−1cxn−2…axnbxn−1cxn−2… 中aa、bb 和 cc 都是各自项的系数。系数决定了每个变量项的影响程度它们可以是实数、复数或其他数学结构的成员。 在一个多项式中通常高阶项对函数的整体形状和行为有着更显著的影响而低阶项和常量则在更小的尺度上调整函数的细节。系数则决定了每个项的具体贡献。系数决定了变量的比例关系和对整个公式的影响程度。它们可以改变公式的斜率、曲线形状和整体大小。 三、时间复杂度分析方法
前面介绍了时间复杂度的由来和表示方法。现在我们介绍一下如何分析一段代码的时间复杂度。下面讲解两个比较实用的法则加法法则和乘法法则。
1、加法法则代码总的复杂度等于量级最大的那段代码的复杂度 大O复杂度表示方法只表示一种变化趋势。我们通常会忽略公式中的常量低阶和系数只记录最大量级。因此在分析一段代码的时间复杂度的时候我们也只需要关注循环执行次数最多的那段代码。 我们来看下面这样一段代码。读者可以先试着分析一下这段代码的时间复杂度然后与作者分析的思路进行比较看看思路是否一致。
public static int cal1(int n){int sum_1 0;int p 1;for (; p 100; p){sum_1 sum_1 p;}int sum_2 0;int q 1;for (; q n; q){sum_2 sum_2 q;}int sum_3 0;int i 1;int j 1;for (; i n; i){j 1;for (; j n; j){sum_3 sum_3 i * j;}}return sum_1 sum_2 sum_3;
} 复杂度分析 2 2 * 1002 2 * n3 2 * n 2 * n^21 2 * n^2 4 * n 208 上述这段代码分为4部分分别是求sum_1sum_2sum_3以及对这3个数求和。我们分别分析每一部分代码的时间复杂度然后把它们放到一起再取一个量级最大的作为整段代码的时间复杂度。 求sum_1这部分代码的时间复杂度是多少尼因为这部分代码循环执行了100次p100一直不变p是个常量所以执行时间是常量。 这里要再强调一下即便这段代码循环执行10000次或100000次只要是一个已知的数与数据规模n无关这也是常量级的执行时间。回到大O时间复杂度的概念时间复杂度表示的是代码执行时间随数据规模n的增长趋势因此无论常量级的执行时间多长它本身对增长趋势没有任何影响在大O复杂度表示法中我们可以将它常量忽略。 求sum_2sum_3以及对这3个数求和这三部分代码的时间复杂度分别是多少尼答案是OnO(n²)常量。读者应该很容易就分析出来就不在赘述了。 综合这4部分代码的时间复杂度我们取其中最大的量级因此整段代码的时间复杂度就为O(n²)。也就是说总的时间复杂度等于量级最大的那部分代码的时间复杂度。这条法则就是加法法则用公式表示出来如下所示 如果 T1(n) O(f(n)) T2(n) O(g(n)) 那么 T(n) T1(n) T2(n) max(O(f(n)), O(g(n))) O(max(f(n), g(n))) 2、乘法法则嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
我们刚讲了复杂度分析中的加法法则再来看一下乘法法则如下所示 如果 T1(n) O(f(n)) T2(n) O(g(n)) 那么 T(n) T1(n) X T2(n) O(f(n)X O(g(n)) O(f(n) X g(n)) 也就是说假设T1(n) O(n)T2(n) O(n²)则T1(n) X T2(n) O(n³)。落实到具体的代码上我们可以把乘法法则看成嵌套循环。我们通过例子来解释一下如下所示
public static void cal(int n){int ret 0;int i 1;for (; i n; i){ret ret f(i);}
}private static int f(int n) {int sum 0;int i 1;for (; i n; i){sum i;}return sum;
} 我们单独观察上述代码中的cal()函数在cal()函数的时间复杂度为T1 O(n)f()函数的时间复杂度为T2(n) O(n)则总的时间复杂度为T(n) T1(n) X T2(n) O(n X n) O(n²)。
四、几种常见的时间复杂度量级 虽然代码千差万别但常见的时间复杂度量级并不多。简单总结一下如图所示这个涵盖了读者今后可以接触的绝大部分的时间复杂度量级。 计算数量级通常是对一个数的大小进行粗略估计以确定它属于哪个数量级。这种估计可以通过以下步骤进行 将数写成科学计数法将数写成形如 a×10ba×10b 的形式其中 1≤a101≤a10 是尾数bb 是指数。例如1234 可以写成 1.234×1031.234×103。 确定尾数 aa 的范围确定尾数 aa 的范围。通常来说aa 范围在 1 到 10 之间。 确定指数 bb 的值指数 bb 表示了数值在数量级上的大小。例如103103 表示数值在数量级上是千级别的。 确定数量级根据指数 bb 的值来确定数量级。例如bb 为 3 表示数值在数量级上是千级别的。 举例来说假设有一个数值是 6.78×1056.78×105。尾数 aa 是 6.78指数 bb 是 5。因为 bb 是 5所以这个数值在数量级上是百万级别的。 注意计算数量级是一个近似值的过程因此结果可能不是精确的但通常足够用于粗略估计 一、时间复杂度 时间复杂度是指执行算法所需要的计算工作量 时间复杂度是用来衡量算法执行时间随着输入大小增加而增加的程度的一个度量。它表示算法的运行时间与输入数据的大小之间的关系。 在计算时间复杂度时通常考虑最坏情况下的运行时间因为这能够给出算法的最差执行时间保证。时间复杂度用大O符号表示通常写作O(f(n))其中n表示输入大小f(n)是一个函数它描述了算法执行所需的时间与n的关系。 例如一个具有时间复杂度O(n)的算法表示当输入大小增加n倍时它的运行时间也将增加n倍。而一个具有时间复杂度O(n^2)的算法表示当输入大小增加n倍时它的运行时间将增加n的平方倍。 时间复杂度的计算可以帮助我们选择合适的算法来解决特定问题并预测算法在实际应用中的性能表现。通常来说我们会选择具有较低时间复杂度的算法尤其是当处理大量数据时。
二、空间复杂度 而空间复杂度是指执行这个算法所需要的内存空间。 空间复杂度是衡量算法空间利用率的度量标准也就是算法在执行过程中所需要的存储空间大小。
在计算空间复杂度时通常会考虑以下几个因素
算法本身所需要的空间例如程序中定义的变量、数组、对象等。
输入数据所占用的空间例如在排序算法中需要占用额外的数组空间来存储输入数据。 算法执行过程中所占用的空间例如在递归算法中每个递归调用都需要分配额外的栈空间。
空间复杂度通常用大O符号O表示与时间复杂度类似。例如如果一个算法的空间复杂度为O(n)则它所需要的存储空间与输入数据的大小n成正比。
在实际应用中除了考虑算法的时间复杂度之外也需要考虑空间复杂度。对于内存有限的嵌入式系统或移动设备等场景空间复杂度的控制非常重要因为过高的空间复杂度会导致程序崩溃或无法运行。
