首页 > 技术文章 > day 11 算法的时间空间复杂度

gddzkw 2021-12-05 11:05 原文

(1).有以下程序:

求输入的n值(除1和n)之外的所有因子之和。

 

 

 分析:这里函数内的循环体i初值不能为零。%是表示“取余”,0除以任何数都不会存在余数的,所有是余数为0.

(2).有以下程序:

形参m(2<=m<=9),在二维数组中存放一张m行m列的表格,有main函数输出
规则如下,使得每一列的数据以每一行首个数字为公差进行递增。

 

 

 分析:主要就是输出显示二维数组,根据输入n的多少,来执行几行几列。

 

(3).有以下程序:

将长整型数中每一位上为偶数的数一次逆向取出,构成一个新数,高位在地位,地位在高位。

eg:25846513——————>输出:6482

 

 

 分析:*t = d*k + *t;····>第一遍写的时候出错,忘记了传过来的是地址,应该解应用操作。这个错误经常考,不易发现。

 

 

 (4).下列数据结果中,属于非线性结构的是【C】

A.循环队列

B.带链队列

C.二叉树

D.带链栈

分析:常见的线性结构:一维数组(栈)、链表、队列

常见的非线性结构:数、森林、图

栈:先进后出

队列:先进先出

(5).有序线性链表进行二分查找的前提是该线性表必须是【有序存储的(二分法)】

(6).一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后序遍历结果为【DEBFCA】

前序遍历:先输出父结点,再遍历左子树和右子树。

中序遍历:先遍历左子树,在输出父节点,再遍历右子树。

后序遍历:先遍历左子树,在遍历右子树,最后输出父节点。

小结:看输出父节点的顺序,就确定是前序、中序还算后序。

(7).算法的空间复杂度是指【A】,算法的时间复杂度是指【E】。

A.算法在执行过程中所需要的计算机存储空间

B.算法所处理的数据量

C.算法程序中的语句或指令条纹

D.算法在执行过程中所需要的临时工作单元数

E.算法在运行过程中所需要的时间

算法复杂度的计算方法:

时间复杂度指算法运行需要的时间,一般将算法的基本运算执行次数作为时间复杂度的度量标准。

 

 

 总执行次数=1+1+n+n+n*n+n*(n+1)=2n^2+2n+1次,T(n^2)=2*n^2+2*n+1.当n足够大时,运行时间取决于最高项。因此后面可以忽略不计,舍小项,舍系数。即用时间复杂度的渐进上界O表示,那么该算法的时间复杂度为O(n^2)。【循环体最内部的循环次数往往是最多的!】

所以:对于一个算法,往往考察最坏的情况是怎样的,而不是考察最好的情况,最坏的情况对于衡量算法的好坏具有实际意义。

 

空间复杂度的计算方法:

空间复杂度是指在运行过程中占用了多少的存储空间,算法占用的存储空间包括:输入输出数据、算法本身、额外需要的辅助空间。

输入输出空间是必须的,算法的占用空间可以通过代码的精简来减免,而在运行是使用的辅助空间,是衡量空间复杂度的关键因素,一般将算法的辅助空间作为衡量空间复杂度的标准。

 

 

 该算法使用了一个辅助空间,即空间复杂度为O(1)

 

推荐阅读