文件名称：中起泡排序-web服务稳定性测试 负载测试 可靠性测试 测试报告
文件大小：10.35MB
文件格式：PDF
更新时间：2024-07-30 10:58:54
数据结构 邓俊辉 清华大学 mooc学堂在线 教材
第1章 绪讳 §1.2 复杂度度量 99 1.2.2 渐进复杂度 至此，对于同一问题的两个算法A和B，通过比较其时间复杂度TA(n)和TB(n)，即可评价二 者对于同一输入规模n的计算效率高低。然而，藉此还不足以就其性能优劣做出总体性的评判， 比如对于某些问题，一些算法更适用于小规模输入，而另一些则相反（习题[1-5]）。 幸运的是，在评价算法运行效率时，我们往往可以忽略其处理小规模问题时的能力差异，转 而关注其在处理更大规模问题时的表现。其中的原因不难理解，小规模问题所需的处理时间本来 就相对更少，故此时不同算法的实际效率差异并不明显；而在处理更大规模的问题时，效率的些 许差异都将对实际执行效果产生巨大的影响。这种着眼长远、更为注重时间复杂度的总体变化趋 势和增长速度的策略与方法，即所谓的渐进分析（asymptotic analysis）。 那么，针对足够大的输入规模n，算法执行时间T(n)的渐进增长速度，应如何度量和评价呢？ 大O记号 同样地出于保守的估计，我们首先关注T(n)的渐进上界。为此可引入所谓“大O记号” （big-O notation）。具体地，若存在正的常数c和函数f(n)，使得对任何n >> 2都有 T(n) c∙f(n) 则可认为在n足够大之后，f(n)给出了T(n)增长速度的一个渐进上界。此时，记之为： T(n) = O(f(n)) 由这一定义，可导出大O记号的以下性质： (1) 对于任一常数c > 0，有O(f(n)) = O(c∙f(n)) (2) 对于任意常数a > b > 0，有O(n a + n b ) = O(n a ) 前一性质意味着，在大O记号的意义下，函数各项正的常系数可以忽略并等同于1。后一性 质则意味着，多项式中的低次项均可忽略，只需保留最高次项。可以看出，大O记号的这些性质 的确体现了对函数总体渐进增长趋势的关注和刻画。 环境差异 在实际环境中直接测得的执行时间T(n)，虽不失为衡量算法性能的一种指标，但作为评判 不同算法性能优劣的标准，其可信度值得推敲。事实上，即便是同一算法、同一输入，在不同的 硬件平台上、不同的操作系统中甚至不同的时间，所需要的计算时间都不尽相同。因此，有必要 按照超脱于具体硬件平台和软件环境的某一客观标准，来度量算法的时间复杂度，并进而评价不 同算法的效率差异。 基本操作 一种自然且可行的解决办法是，将时间复杂度理解为算法中各条指令的执行时间之和。在图 灵机（Turing Machine, TM）和随机存储机（Random Access Machine, RAM）等计算模型 [4] 中，指令语句均可分解为若干次基本操作，比如算术运算、比较、分支、子程序调用与返回等； 而在大多数实际的计算环境中，每一次这类基本操作都可在常数时间内完成。 如此，不妨将T(n)定义为算法所执行基本操作的总次数。也就是说，T(n)决定于组成算法 的所有语句各自的执行次数，以及其中所含基本操作的数目。以代码1.1中起泡排序 bubblesort1A()算法为例，若将该算法处理长度为n的序列所需的时间记作T(n)，则按照上述 分析，只需统计出该算法所执行基本操作的总次数，即可确定T(n)的上界。