2.1.6 时间复杂度
算法的时间复杂度计算方法
算法的时间复杂度是数据结构中的重要理论基础,也是较难理解和掌握的问题之一。本节总结了计算时间复杂度的方法。
计算算法的时间复杂度的具体步骤如下。
(1)找出算法中的基本语句。算法中执行次数最多的那条语句就是基本语句,通常它是最内层循环的循环体。
(2)计算基本语句的执行次数的数量级。只计算最高次幂的,忽略所有低次幂和最高次幂的系数。
(3)用O()记号表示算法的时间复杂度。将基本语句执行次数的数量级放入O()记号中。对于并列循环,忽略;对于嵌套循环,相乘。例如,若一层循环的时间复杂度为O(n),两层循环的时间复杂度就是O(n2),依此类推。
常见的算法时间复杂度由小到大依次如下。
Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)
2.1.7 笔试题和面试题
试题1.在一个长度为n的顺序存储线性表中,向第i个元素(1≤i≤n+1)之前插入一个新元素,需要从后向前依次后移几个元素?当删除第i个元素时,需要从前向后前移几个元素?
分析:考查线性表中顺序存储的特点。
答案:n-i+1,n-i。
试题2.已知链表的头节点head,写一个函数把该链表逆序。
分析:考查线性表中链表逆序算法。
答案:
void List::reverse()
{
list_node*p=head;
list_node*q=p->next;
list_node*r=NULL;
while(q){;
r=q->next;
q->next=p;
p=q;
q=r;
}
head->next=NULL;
head=p;
}?
试题3.找出单向链表中的中间节点。
分析:有两个指针,一个指针的步长为1,另一个指针的步长为2。步长为2的指针指向链表末尾后步长为1的指针正好指向链表中间。
答案:
list_node*List::middleElement()
{
list_node*p=head;
list_node*q=head->next;
while(q){;
p=p->next;
if(q)q=q->next;
if(q)q=q->next;
}
}
试题4.如何检查一个单向链表中是否有环?
分析:同样有两个指针,一个指针的步长为1,另一个指针的步长为2,如果两个指针能相遇则有环。
答案:
list_node*List::getJoinPointer()
{
if(head==NULL||head->next==NULL)return NULL;
list_node*one=head;
list_node*two=head->next;
while(one!=two){
one=one->next;
if(two)two=two->next;
else break;
if(two)two=two->next;
else break;
};
if(one==NULL||two==NULL)return NULL;
return one;
}
试题5.给定单链表,如果有环则返回,从头节点(head)进入环的第1个节点。
分析:如果有环,那么p1与p2的重合点p必然在环中。从p点断开环,方法为令p1=p,p2=p->next,p->next=NULL。此时,原单链表可以看作两个单链表,一个从head开始,另一个从p2开始,于是运用本节中试题2的方法,我们找到它们的第一个交点即可。
答案:
list_node*List::findCycleEntry()
{
if(checkCycle()==false)return NULL;
list_node*joinPointer=getJoinPoiter();
list_node*p=head;
list_node*q=joinPointer->next;
While(p!=q)
{
p=p->next;
q=q->next;
}
return p;
}?
试题6.只给定单链表中某个节点p(并非最后一个节点,即p->next!=NULL),删除该节点。
分析:将p后面那个节点的值复制到p,删除p后面的节点。
答案:
void List::deleteByPointer(list_node*node)
{
if(node)
{
if(node->next){
node->value=node->next->value;
node->next=node->next->next;
}
}
}
试题7.在单链表节点p前面插入一个节点。
分析:首先在p后面插入一个节点,然后将p的值与后面一个节点的值互换。
答案:类似于本节中试题6的答案,此处省略。
试题8.给定单链表头节点,删除链表中倒数第k个节点。
分析:第一个指针指向链表头,第二个指针指向第k个节点,然后两个指针一起移动,若第二个指针指向链表末尾,则第一个指针指向倒数第k个节点。
答案:
list_node*List::lastKelement(int k){
Int t=k;
list_node * p = head;
while(p&&t){
p=p->next;
t--;
}
if(p==NULL&&t>0)return NULL;
list_node*q=head;
while(q&&p){
p=p->next;
q=q->next;
}
return q;
}
试题9.判断两个链表是否相交。
分析:有两种情况。如果链表中有环,则先在环里设定一个不动的指针,另一个链表的指针从头开始移动。如果另一个链表的指针能够与环中的指针相遇,则两个链表相交。如果链表中没有环,则判断两个链表的最后一个节点是否相同。若相同,则两个链表相交。
答案:
bool List::isIntersecting(const List & list)
{
bool flag=false;
if(this->checkCycle( ))
{
list_node*p=getJoinPointer( );
list_node*q=list.head;
while(q){
if(q==p){;
flag=true;
break;
}
q=q->next;
}
flag=true;
}
else
{
list_node*p=head;
list_node*q=list.head;
while(p->next)p=p->next;
while(q->next)q=q->next;
if(p==q)flag=true;
else flag=false;
}
Return flag;
}
试题10.若两个链表相交,找出交点(2009年华为校园招聘笔试题)。
分析:求出两个链表的长度a和b,一个指针指向较短链表的头head,另一个指针指向较长链表的第(head+|a?b|)个节点,然后两个指针一起移动,相遇处即为交点。
答案:
list_node*List::intersectNode(const List&list)
{
if(!isIntersecting(list))return NULL;
int a=cnt;
int b=list.cnt;
list_node*p;
list_node*q;
if(a<b){p=list.head;q=head;}
else{p=head; q=list.head;}
a=abs(cnt–list.cnt);
while(p&&a)
{
p=p->next;
a--;
}
while(p&&q)
{
if(q==p)break;
p=p->next;
q=q->next;
}
if(p&&q&&p==q)return p;
return NULL;
}
试题11.实现库函数strcpy(char * des, const char * src)。
答案:注意要点见2.1.2节。
试题12.请说出树的深度优先、广度优先搜索,以及非递归实现的特点。
分析:该题考核的树的两种遍历方法,见2.1.3节。
答案:深度优先搜索是一条分支一条分支进行遍历的,广度优先搜索是一层一层进行遍历的;深度优先的非递归实现利用栈,广度优先的非递归实现利用队列。其具体实现见2.1.3节。
试题13.对于一棵二叉树,如何判断它是否是完全二叉树?
分析:考查二叉树的特性,二叉树的第5条特性是关于完全二叉树的。
答案:如果二叉树的最大节点为i,父节点是i/2,那么它就是完全二叉树。
试题14.一个典型的大型项目通常由众多模块构成,在构建整个系统时,这些模块之间复杂的编译依赖是让人头疼的地方之一。现在就有这样的一个大型项目,它由N(N>1000)个模块构成,每个模块都是可以编译的,但模块之间存在编译依赖,如模块N1依赖N2,即编译N1时,N2必须已经先编译完成,否则N1不能完成编译,但模块之间没有循环依赖的问题。请设计一种快速算法,以完成整个项目的编译构建过程,并给出算法的时间复杂度。
图2.9 N个模块的关系
分析:按照题意,假设N=8,将8个模块的关系画出来(注意,不能循环依赖,一个模块可以依赖多个其他模块,一个模块可以被多个模块依赖),如图2.9所示。其中S表示编译起点,E表示编译终点,箭头指向表示被依赖关系,即N5依赖N1、N2、N3这3个模块。
由此可以看出,合理的编译流程应该是从S出发,当一个节点的前驱节点都编译完成后,该节点才可以编译。该题考查的是图的遍历的灵活运用。
可以考虑从S开始对节点深度进行标号,起始深度为0。使用广度优先搜索算法扫描节点,对未标记过深度的节点,深度加1。对比已标记过的节点深度(已标记深度)和上一个节点的深度加1后的值,取最大值。按照该深度标记完整张图之后,假设最大深度为k,建立大小为k的链表a。再次扫描所有节点,将深度为1的节点链接到a[1],深度为m的节点链接到a[m]。最后,从a[1]编译执行到a[m]。
答案:
{
string modeName;
Int depth=-1;
arrayList <node> nextNodes;
}
Int MaskTask(node PreTask) //利用队列,采用图的广度搜索算法给节点加上深度标记
{ Queue*queue;
Int maxDepth=0;
preTask.depth=0;
queue.push(preTask);
While(!queue.isEmpty())
{
node tmp=queque.pop();
ArrayList <node> nexts=tmp.nextNodes;
For(int i=0;i<nexts.lenths;i++)
{
If(nexts[i].depth==-1)
{
nexts[i].depth=tmp.depth+1;
tmp.push(nexts[i]);
}
Else
{
If((tmp.depth+1)>nexts[i].depth)
{
nexts[i].depth=tmp.depth+1;
tmp.push(nexts[i]);
}
}
maxDepth=nexts[i].depth;
}
Return maxDepth;
}
arraylist SortTask(node PreTask,int maxDepth)//将标记的节点整理排序
{
Queue element;
ArrayList nodelist;
For(int i=0;i<maxDepth;i++)
{
Nodelist.add(new arraylist());
}
Element.push(preTask);
While(!element.isEmpth())
{
Node tmp=element.pop();
Int tmpDepth=tmp.depth;
If(Nodelist[tmpDepth-1].Notexist(tmp))
{
Nodelist[tmpDepth-1].add(tmp);
}
For(int j=0;j<=tmp.nextNodes.length;j++)
{
Element.push(tmp.nextNodes[j]);
}
}
Return nodelist;
}
Void DoCompile( Node PreTask)
{ int depth=MaskTask(Node PreTask);
Arraylist nl=SortTask(Node PreTask,depth);
For(int i=0;i<nl.length;i++)
{ arraylist al=nl[i];
For(int j=0;j<=al.length;j++)
{
Comile(al[j]);//编译节点
}
}
}
通过广度优先搜索算法计算节点深度的时间复杂度为O(n+e),其中n为节点个数,e为边数。扫描完后节点分类的时间复杂度也是O(n+e),编译的时间复杂度为O(n)。因此,整个算法的时间复杂度为O(n)。
试题15.如果有一个大文本文件(保存各种词语),每次搜索都必须检查查询词是否在这个大文件中,请问通过什么方式能够提高查找效率?请讲解所使用的算法。
分析:考查基本数据结构,灵活采取算法处理实际问题的能力,快速编程能力,在给出一定提示的情况下,检查学习能力和知识应用能力。
答案:基本方法是采用哈希签名,提高匹配效率;建立多叉树,保存文件数据,提高查找速度。
较优方法是在上面的基础上,将文本文件转化为key->value的二进制文件,提高文件操作和查找速度。
更优方法是在上面的基础上,开辟内存作为调整缓存,保存高频率查询词,提高整体查找效率,如给出缓存的更新机制。
试题16.函数void log(int, char, long)调用栈的结构是什么样的?
分析:考查函数压栈的顺序、字节对齐等。
答案:按照从右到左的压栈顺序,注意高地址和低地址,压栈时以机器字长为单位且所有参数按字对齐,栈的结构如图2.10所示。
图2.10 栈的结构
试题17.有一份成绩单,只有两个字段,即姓名和成绩,数据量在百万级别。要求用最优的数据存储方式,通过姓名快速查找出成绩。
答案:哈希存储。
试题18.快速排序的平均时间复杂度是多少?最坏时间复杂度是多少?在哪些情况下会出现最坏时间复杂度?
分析:考查排序算法。
答案:快速排序算法的时间复杂度为O(nlog2n),最坏时间复杂度为O(n2),在待排序列正序或者逆序的情况下会出现最坏时间复杂度。
试题19.请用你熟悉的任意语言实现一个冒泡算法,并写出它的时间复杂度。
分析:考查基本算法知识。
答案:见2.1.5节。
试题20.栈和队列的共同特点是什么?
分析:考查栈和队列的概念。
答案:栈和队列都只能在端点处插入与删除元素。
试题21.栈通常采用的两种存储结构是什么?
分析:栈属于线性表的一种,线性表的存储结构有两种。
答案:顺序存储结构和链式存储结构。
试题22.下列关于栈的叙述正确的是( )。
A.栈具有非线性结构B.栈具有树状结构
C.栈具有先进先出的特征D.栈具有后进先出的特征
分析:考查栈的概念。
答案:D。
试题23.链表不具有的特点是( )。
A.不必事先估计存储空间B.可随机访问任意元素
C.插入和删除操作中不需要移动元素D.所需空间与线性表长度成正比
分析:该题考查链表的特点,B属于顺序存储结构的特点。
答案:B。
试题24.链表的优点是什么?
分析:考查链表的特点。
答案:便于插入和删除操作,动态申请空间。
试题25.线性表若采用链式存储,要求内存中可用的存储单元地址( )。
A.连续B.部分地址连续
C.一定不连续D.连续、不连续都可以
分析:考查链表的特点。
答案:D。
试题26.在深度为5的满二叉树中,叶子节点的个数是多少?
分析:考查二叉树的特性及满二叉树的概念。满二叉树中叶子节点的个数为。注意,不要按照完全二叉树计算。
答案:31。
试题27.已知二叉树后序遍历结果是dabec,中序遍历结果是debac,它的前序遍历结果是什么?
分析:考查二叉树的遍历方式,2.1.3节中有讲解,先画出二叉树,再遍历。
答案:cedba。
试题28.已知二叉树前序遍历结果与中序遍历结果分别是ABDEGCFH和DBGEACHF,则该二叉树的后序遍历结果是什么?
分析:同本节的试题27。
答案:DGEBHFCA。
试题29.字符串的长度定义是什么?
分析:考查串的概念。
答案:字符串中所包含的字符个数。
试题30.判断两个数组中是否存在相同的数字。给定两个排好序的数组,怎样高效判断这两组数中有相同的数字?
分析:首先考虑时间复杂度为O(nlog2n)的算法。任意挑选一个数组,遍历该数组的所有元素。在遍历过程中,在另一个数组中对第1个数组中的每个元素进行二叉树搜索。还可以采用时间复杂度为O(n)的算法,因为两个数组都是排好序的,所以只需要遍历一次即可。
答案:首先设置两个索引,分别初始化为两个数组的起始地址,然后依次向前推进。推进的规则是比较两个数组中的数字,小的数组的索引向前推进一步,直到任何一个数组的索引到达数组末尾。若此时还没有碰到相同的数字,则说明数组中没有相同的数字。
试题31.在需要经常查找节点的前驱和后继的场合中,使用( )比较合适。
A.单链表B.双链表C.顺序链表D.循环链表
分析:考查链表的运用。
答案:B。
试题32.对长度为n的线性表进行顺序查找,在最坏情况下所需要的比较次数是多少?
分析:考查查找算法。
答案:最坏情况下比较n次。
试题33.最简单的交换排序方法是什么?
答案:冒泡排序。
试题34.线性表的长度为n,在最坏情况下,冒泡排序需要的比较次数是多少?
分析:考查冒泡排序。
答案:n(n?1)/2。
试题35.在待排序元素基本有序的前提下,效率最高的排序方法是什么?
答案:冒泡排序。
试题36.在最坏情况下,时间复杂度最小的排序方法是什么?
答案:堆排序。
试题37.堆排序法属于什么排序?
答案:选择排序。
试题38.对N个数进行快速排序算法的平均时间复杂度是多少?
分析:见2.1.5节中表2.1。
答案:O(Nlog2N)。
试题39.把整数转换成字符串。
分析:2.1.2节中有算法描述。
答案:
/*把整数转化成字符串*/
char *IntToStr(int num,char str[])
{
int i=0,j=0;
char temp[100];
while(num)
{
temp[i]=num%10+'0';
num=num/10;
i++;
}
temp[i]=0; //字符串结束标志
i=i-1; //回到temp中最后一个有意义的数字
while(i>=0)
{
str[j]=temp[i];
i--;
j++;
}
str[j]=0; //字符串结束标志
return str;
}
试题40.判断以下8位二进制数(补码形式)的加法运算是否会产生溢出。
(a)11000010+00111111
(b)00000010+00111111
(c)11000010+11111111
(d)00000010+11111111
分析:手动进行计算,判断依据是正数+正数=负数,负数+负数=正数。
答案:
(a)11000010+00111111表示负数+正数,不可能溢出。
(b)00000010+00111111=01000001,正数+正数=正数,没有溢出。
(c)11000010+11111111=11000001,负数+负数=负数,没有溢出。
(d)00000010+11111111表示正数+负数,不可能溢出。
试题41.在不借助第3个变量的情况下,互换两个int类型的变量X、Y的值,用任何自己熟悉的编程语言完成。
分析:思路为X=X+Y,Y=X?Y,X=X?Y。
答案:略。
试题42.请问以下代码有什么问题?
int main()
{
char a;
char *str=&a;
strcpy(str,"hello");
printf(str);
return 0;
}
答案:没有为str分配内存空间,因此将发生异常。问题出在将一个字符串复制进一个字符变量指针所指地址。虽然以上代码可以正确输出结果,但会因为越界进行内存读写而导致程序崩溃。
版权声明:51Testing软件测试网获得人民邮电出版社和作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。