[入门级问题]请教一段程序的时间复杂度!
void fun3(int n)
{
int i=0,s=0;
while (s <n)
{
i++;
s=s+i;
}
}
具体怎么分析这段程序的复杂度.
[解决办法]
第一个是n^(1/2)；
第二个要看用什么方法,
直接建链表应该是n^2;
如果先排序，再建链表，肯定可以到nlogn；
[解决办法]
下来后我又想了一下，答案确实应该是O(N^1/2)。这里的时间复杂度是个循环的次数有关，而循环的次数又和输入的参数n有关：
设迭代的次数是K,则：
K(K+1)/2 = N
在N很大的情况下，==> K^2 = 2N
===> 这样就可以得出时间复杂度是O(N^1/2);
