求时间复杂度的题度
来源：蜘蛛抓取(WebSpider)
时间：2018-09-25 00:44
标签：
求时间复杂度的题
我知道应该是k(k+1)/2=n算出来是(根号(8*n+1)-1)/2我的問题是为什么根号(8n+1)/2的时间复杂度就是根号n而不是根号2n呢？为什么理由是什么？求大神的详细解答这个问题把我困扰住... 我知道应该是k(k+1)/2=n 算出来是(根号(8*n+1) - 1 ) /2
我的问题是，为什么根号(8n+1)/2的时间复杂度就是根号n 而不是根号2n呢为什么？理由是什么求大神的详细解答，这个问题把我困擾住了！
可选中1个或多个下面的关键词搜索相关资料。也可直接点“搜索资料”搜索整个问题
渐进时间复杂度是个近似值，n越趋近无窮大越接近准确值
舍去项的常数系数，你可以把这个看看作一条为了方便的书写约定哪怕有100条语句复杂度也是O(1)。
因为如果不这样做的話你用什么来决定项的系数？C语言程序的行数还是编译之后汇编语言的行数？这样准确吗如果是长的复杂C语言语句呢？而且不同平囼编译产生的字节码条数也可能不同所以你没法准确的确定这个系数，干脆就把他舍去只考量n的数量级就够了。
好的我理解了，不過我还要问如果碰到选择题，其中有一个是根号2n的选项怎么办呢？是不是都是选根号n不管系数如何？
是的但是如果选项里只有O(2n)的話选他也讲得通。
根号2n=根号2*根号n＝1.414*根号n1.414是常数项舍去，故
这个你要看时间复杂度是怎么定义的，为了剔除机器和程序设计技巧对运行時间的影响在计算时间复杂度时考虑的是运行的次数，正如你所说上述问题的算出来是根号2n,根号2n又等于根号2乘以根号n,此时我们就认为咜的复杂度是根号n，因为根号2可以看成是它的一个线性系数随着输入规模n的增加是可以忽略的
