算法和算法分析
标签: 算法和算法分析
学习人数: 12493

全屏播放
赞赏支持

算法的基本概念

对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。

 

根据以上定义,可以知道,算法一定是可以解决特定问题的,其次,它是有限的,然后,每一个指令都表示特定的操作。于是可以知道算法的五个特性:

有穷性:一个算法必须在执行有穷步之后结束,且每一步都必须在有穷时间内完成。如果有类似无限循环的语句,那么就不能称之为算法。
可行性:一个算法是可行的,即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。每一步操作都是可以实现的才能称之为算法。
确定性:算法中每条指令、每条语句必须有确切的含义,相同的输入必须得出到相同的输出,不能产生二义性。
输入:一个算法必须有零个或多个输入。
输出:一个算法必须有一个或多个输出。

 

算法为什么是有穷的?在操作系统中使用了很多无穷的代码语句,它们也是非常有用的,它们不是算法,那它们又是什么?

 

对此,引入一个程序的概念,什么是算法,什么又是程序

根据上面的算法的定义,可以...

登录查看完整内容


课后作业

课后习题

 

【2019年真题】设n是描述问题规模的非负整数,下列程序段的时间复杂度是

x = 0;  
while (n >= (x + l) * (x + l))  
x = x + l;  

A. O(log2n)      B. O(n1/2)       C. O(n)       D. O(n2)

参考答案:B

 

【2017年真题】下列函数的时间复杂度是

int func(int n) {  
    int i=0, sum=0;  
    while (sum < n) sum += ++i;  
    return i;  
}  

A.O(log2n)        B.O(n1/2)        C.O(n)        D.O(nlog2n)

参考答案:B


【2014年真题】下列程序段的时间复杂度是()。

count = 0;  
for (k = 1; k <= n; k *= 2)  
    for (j = 1; j <= n; j++)  
        count++;  

A.O(log2n)        B.O(n)    C.O(nlog2n)    D.O(n2)

参考答案:C
答案解析:内层循环条件 j<=n 与外层循环的变量无关,每次循环 j 自增 1,每次内层循环都执行 n 次。外层循环条件为 k<=n,增量定义为 k*=2,可知循环次数为 2k <=n,即 k<=log2n。
所以内层循环的时间复杂度是 O(n),外层循环的时间复杂度是 O(log2n)。对于嵌套循环,根 
据乘法规则可知,该段程序的时间复杂度 T(n)=T1(n)*T2(n)=O(n)*O(log2n)=O(nlog2n)。 


【2013年真题】已知两个长度分别为 m 和 n 的升序链表,若将它们合并为一个长度为 m+n 的降序链表,则最坏情况下的时间复杂度是()
A. O(n)         B. O(m * n)     C. O(min(m, n))         D. O(max(m, n))

参考答案:D
答案解析:m、n 是两个升序链表,长度分别为 m 和 n。在合并过程中,最坏的情况是两个链表中的元素依次进行比较,比较的次数最少是 m 和 n 中的最小值。 


【2012年真题】求整数 n(n≥0)阶乘的算法如下,其时间复杂度是()

int fact(int n){  
    if (n <= 1) return 1;  
    return n * fact(n - 1);  
}  

A. O(log2n) 
B. O(n) 
C. O(nlog2n) 
D. O(n2)

参考答案:B
答案解析:考查时间复杂度的计算。 
该程序中使用了递归运算。本题中递归的边界条件是 n<=1,每调用一次 fact(),传入该层 fact()的参 数值减 1(注意不是 n 减 1),因此执行频率最高的语句是 return n*fact(n-1),一共执行了 n-1 次,而每一层 fact(i)运算只包含一次乘法。如果采用递归式来表示时间复杂度,则:

时间复杂度为 O(n)。 


【2011年真题】设 n 是描述问题规模的非负整数,下面程序片段的时间复杂度是()

x = 2;  
while (x < n/2)  
x = 2 * x;  

A.O(log2n) 
B.O(n) 
C.O(nlog2n)
D.O(n2

解答:A。程序中,执行频率最高的语句为“x=2*x”。设该语句执行了t次,则2 t+1=n/2, 
故t=log2(n/2)-1=log2n-2= O(log2n)。


登录后发布评论

暂无评论,来抢沙发