1 O(1)⎯⎯取非极端元素

给定整数子集S, +∞ > |S| = n ≥ 3,从中找出一个元素a∈S,使得a ≠max(S)且a ≠ min(S)。也就是说,在最大、最小者之外,取出任意一个数。
既然 S 是有限集,故其中的最大、最小元素各有且仅有一个。因此,无论 S 的规
模有多大,在前三个元素 S[0]、S[1]和 S[2]中,必包含至少一个非极端元素。于是,我们可以取 x =
S[0]、y = S[1]和 z = S[ 2],这只需执行三次基本操作,耗费 O(3)时间。接下来,为了确定这三个元
素的大小次序,我们最多需要做三次比较(请读者自己给出证明),也是 O(3)时间。最后,输出居中的那个元素只需 O(1)时间。
综合起来,算法的运行时间为:
T(n) = O(3) + O(3) + O(1) = O(7) = O(1)
也就是说,算法具有常数的时间复杂度。


2 O(logn)⎯⎯进制转换

给定任一十进制整数,将其转换为三进制表示。比如
23(10) = 212(3)
101(10) = 10202(3)
第一轮循环,输出 101 mod 3 = 2,n = 100/3 = 33;第二轮循环,输出 33 mod
3 = 0,n = 33/3 = 11;第三轮循环,输出 11 mod 3 = 2,n = 11/3 = 3;第四轮循环,输出 3 mod 3
= 0,n = 3/3 = 1;第五轮循环,输出 1 mod 3 = 1,n = 1/3 = 0,至此算法结束。请注意,以上各个
数位是按照从低到高的次序输出的,所以转换后的结果应该是 10202(3)。
实际上,对 算法一.5 稍作修改,即可推广至任意进制,请读者自行完成这一任务。
我们以整数n的大小作为输入规模,来分析 算法一.5 的运行时间。该算法由若干次循环构成,
每一轮循环内部,都只需进行两次基本操作(取模、整除)。为了确定需要进行的循环轮数,我们可以注意到以下事实:每经过一轮循环,n都至少减少至 1/3。于是,至多经过 1+⎣log3n⎦次循环,即可减小至 0。
也可以从另一个角度来解释这一结果。该算法的任务是依次给出三进制表示的各个数位,其中
的每一轮循环,都恰好给出其中的一个数位。因此,总共需要进行的循环轮数,应该恰好等于 n 的三进制表示的位数,即 1+⎣log3n⎦。因此,该算法需要运行 O(2×(1+⎣log3n⎦)) = O(log3n)时间。鉴于大 O 记号的性质,我们通常会忽略对数函数的常底数。比如这里的底数为常数 3,故通常将上述复杂度记作 O(logn)。请读者根据大 O 记号的定义证明:就渐进复杂度的意义而言,对数函数的常底数具体是多少是无所谓的。此时,我们称这类算法具有对数的时间复杂度.


3 O(n)⎯⎯数组求和

算法:Sum(A[], n)
输入:由n个整数组成的数组A[]
输出:A[]中所有元素的总和
{
令s = 0;
对于每一个A[i],i = 0, 1, …, n-1
令s = s + A[i];
}
首先,对s的初始化需要O(1)时间。算法的主体部分是一个循环,每一轮循环中只需进行一次累加运算,这属于基本操作,可以O(1)时间内完成。每经过一轮循环,都对一个元素进行累加,故总共需要做n轮循环。因此,算法的运行时间为
O(1) + O(1)×n = O(n+1) = O(n)


4 O(n2)⎯⎯冒泡排序

为了对n个整数排序,该算法的外循环最多需要做n轮。经过第i轮循环,元素
S[n-i-1]必然就位,i = 0, 1, …, n-1。在第i轮外循环中,内循环需要做n-i-1 轮。在每一轮内循环中,
需要做一次比较操作,另外至多需要做三次赋值操作,这些都属于基本操作,可以在O(4)的时间内完成。因此,该算法总共需要的运行时间为:
T(n)= O(2n(n-1)) = O(2n^2– 2n)
鉴于大 O 记号的特性,低次项可以忽略,常系数可以简化为 1,故再次得到
T(n) = O(n^2)
我们称这类算法具有平方时间复杂度。对于其它一些算法,n 的次数可能更高,但只要其次数为常数,我们都统称之为“多项式时间复杂度”。另外,对于任意的n > 0,都存在规模为n的输入序列,使得算法的确需要运行Ω(n^2)时间才能完成对该序列的排序(请读者自行构造这样的实例),故这一复杂度上界是紧的。既然如此,更准确地,我们应该记之为
T(n) = Θ(n^2)。


5 O(2^r)⎯⎯幂函数

输入:非负整数r
输出:幂2^r
{
power = 1;
while (0 < r--)
power = power * 2;
return power;
}
需要做r次迭代,每次迭代只涉及常数次基本操作,故总共需要运行O(r)时间。按
照如上定义,问题的输入规模为n,故有O(r) = O(2^n)。

Last modification:March 31st, 2020 at 02:09 pm
如果觉得我的文章对你有用,请随意赞赏