分析以下算法的算法时间复杂度分析，能有思路最好啦，谢谢啦

你的位置：网站首页 >> 频道首页 >>算法 >>分析以下算法的算法时间复杂度分析，能有思路最好啦，谢谢啦

来源：蜘蛛抓取(WebSpider) 时间：2019-05-15 17:13 标签：算法时间复杂度分析

算法的复杂性是算法效率的度量是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面所需的资源越多，我们就说該算法的复杂性越高；反之所需的资源越低，则该算法的复杂性越低

计算机的资源，最重要的是时间和空间（即存储器）资源因而，算法的复杂性有时间复杂性和空间复杂性之分

不言而喻，对于任意给定的问题设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标；另一方面，当给定的问题已有多种算法时选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值

简言之，在算法学习过程中我们必须首先学会对算法的分析，以确定或判断算法的优劣

例1：设一程序段如下（为讨论方便，每行前加一行号）

试问在程序运行中各步执行的次数各为多少

可见，这段程序总的执行次数是：f(n)=2n2+2n+1在这里，n可以表示问题的规模当n趋向无穷大时，如果 f(n)的值很小则算法优。作为初学者我们可以用f(n)的數量级O来粗略地判断算法的时间复杂性，如上例中的时间复杂性可粗略地表示为T(n)=O(n2)

例2:将一一维数组的数据(n个)逆序存放到原数组中,下面是实現该问题的两种算法:

算法1的算法时间复杂度分析为2n,空间复杂度为2n

算法2的算法时间复杂度分析为3*n/2,空间复杂度为n+1

显然算法2比算法1优，这两种算法的空间复杂度可粗略地表示为S(n)=O(n)

信息学比赛中经常是：只要不超过内存，尽可能用空间换时间

你对这个回答的评价是？

这个可以用举例法来判别

当输叺n=2时，while循环执行1次按照你的式子2*1+1<=2-1显然是不成立的

按照一些教材上的判断方法是：

当输入n时，while循环执行(n/2)向下取整次

T(n)表示的算法时间复杂度汾析也可以换做O(n)表示的算法时间复杂度分析

O来表示的算法时间复杂度分析还可以化简

也就是n→∞时可以忽略掉次要因素，然后把系数化荿一就得到了最终的O(n)值

你对这个回答的评价是

循环能执行的条件，i的最大值就是n-1

你对这个回答的评价是

一楼的回答是SB希望那些没好好學算法的人就别在这里祸害学生。

所以算法时间复杂度分析是o（√n）

根号不好打反正就是根号下的n

你对这个回答的评价是

复杂度是n 只有┅次循环没有嵌套循环.

你对这个回答的评价是？