文件名称：算法复杂度及其分析-一种新的超宽带脉冲波形设计方法
文件大小：3.72MB
文件格式：PDF
更新时间：2024-07-09 04:02:51
数据结构
第一章 算法及其复杂度 §1.3 算法复杂度及其分析 11 §1.3 算法复杂度及其分析 我们不仅要了解算法复杂度的度量规则，更要学会如何对各个具体算法的复杂度进行分析。在 第 1.2.2 节所引入的度量算法复杂度的三种记号中，大O记号是 基本的，也是 常用到的。按照渐 进复杂度的思想，可以将算法的复杂度按照高低划分为若干典型的级别。 1.3.1 O(1)⎯⎯取非极端元素 首先来看这样一个问题：给定整数子集S, +∞ > |S| = n ≥ 3，从中找出一个元素a∈S，使得a ≠ max(S)且a ≠ min(S)。也就是说，在 大、 小者之外，取出任意一个数。这一问题可以用 算法一.4 解决： 算法：NonextremeElement(S[], n) 输入：由n个整数构成的集合S 输出：其中的任一非极端元素 { 任取的三个元素x, y, z ∈ S; //既然S是集合，这三个元素必互异 通过比较，找出其中的最小者min{x, y, z}和最大者max{x, y, z}; 输出最小、最大者之外的那个元素; } 算法一.4 取非极端元素 算法一.4 的正确性不言而喻，但它需要运行多少时间呢？与输入的规模n有何联系？ 我们注意到，既然 S 是有限集，故其中的 大、 小元素各有且仅有一个。因此，无论 S 的规 模有多大，在前三个元素 S[0]、S[1]和 S[2]中，必包含至少一个非极端元素。于是，我们可以取 x = S[0]、y = S[1]和 z = S[ 2]，这只需执行三次基本操作，耗费 O(3)时间。接下来，为了确定这三个元 素的大小次序，我们 多需要做三次比较（请读者自己给出证明），也是 O(3)时间。 后，输出居中 的那个元素只需 O(1)时间。 综合起来，算法一.4 的运行时间为： T(n) = O(3) + O(3) + O(1) = O(7) = O(1) 也就是说，算法一.4 具有常数的时间复杂度。 1.3.2 O(logn)⎯⎯进制转换 考虑如下问题：给定任一十进制整数，将其转换为三进制表示。比如 23(10) = 212(3) 101(10) = 10202(3) 这一问题可以由 算法一.5 解决：