摘要:建站服务器 1、常见的算法的时间复杂度比较:常见的算法时间复杂度由小到大依次为: Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)<…<Ο(2)<Ο(
建站服务器
1、常见的算法的时间复杂度比较:
常见的算法时间复杂度由小到大依次为:
Ο(1)<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n2)<Ο(n3)<…<Ο(2)<Ο(n!)
Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)。Ο(logn)、Ο(n)、Ο(nlogn)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法,把这类问题称为P类问题,而把后者称为NP问题。
这只能基本的计算时间复杂度,具体的运行还会与硬件有关。
2、计算时间复杂度的相关题目;
一、单项选择题
1.一个算法应该是( )。
A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D. A和C
1. B
程序不一定满足有穷性,如死循环、操作系统等,而算法必须有穷。算法代表了对问题求解步骤的描述,而程序则是算法在计算机上的特定的实现。
2.某算法的时间复杂度为O(n2),表明该算法的( )。
A.问题规模是n2 B.执行时间等于n2
C.执行时间与n2成正比 D.问题规模与n2成正比
2. C
时间复杂度为O(n2),说明算法的执行时间T(n)<=c * n2(c为比例常数),即T(n)=O(n2),时间复杂度T(n)是问题规模n的函数,其问题规模仍然是n而不是n2。
3.以下算法的时间复杂度为( )。
void fun(int n) {
int i=l;
while(i<=n)
i=i*2;
}
A. O(n) B. O(n2) C. O(nlog2n) D. O(log2n)
3. D
基本运算是i=i*2,设其执行时间为T(n),则2T(n)<=n,即T(n)<=log2n=O(log2n)。
4.设n是描述问题规模的非负整数,下面程序片段的时间复杂度是()。
x=2;
while(x<n/2)
x=2*x;
A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2)
4. A
在程序中,执行频率最高的语句为“x=2*x”。设该语句共执行了 t次,则2t+1=n/2,故t=log2(n/2)-1=log2n-2,得 T(n)=O(log2n)。
5.【2012年计算机联考真题】
求整数n (n>=0)阶乘的算法如下,其时间复杂度是( )。
int fact(int n){
if (n<=l) return 1;
return n*fact(n-1);
}
A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2)
5. B
本题是求阶乘n!的递归代码,即n*(n-1)*...*1共执行n次乘法操作,故T(n)=O(n)。
6.有以下算法,其时间复杂度为( )。
void fun (int n){
int i=0;
while(i*i*i<=n)
i++;
}
A. O(n) B. O(nlogn) C. D.
7.程序段
for(i=n-l;i>l;i--)
for(j=1;j<i;j++)
if (A[j]>A[j+l])
A[j]与 A[j+1]对换;
其中n为正整数,则最后一行的语句频度在最坏情况下是( )。
A. O(n) B. O(nlogn) C. O(n3) D. O(n2)
8.以下算法中加下划线语句的执行次数为()。
int m=0, i, j;
for(i=l;i<=n;i++)
for(j=1;j<=2 * i;j++)
m++;
A. n(n+1) B. n C. n+1 D. n2
相关文章推荐
虚拟主机的专业参数,分别都是什么意思?2022-09-09
中非域名注册规则是怎样的?注册域名有什么用处? 2022-01-10
HostEase新年活动促销 美国/香港主机全场低至五折2021-12-28
HostGator下载完整备份教程分享2021-12-28
Flink中有界数据与无界数据的示例分析2021-12-28