UC知道关于时间复杂度
来源：百度知道 编辑：UC知道 时间：2024/06/06 18:00:02
i:=0;
s:=0;
while s<n do
begin i:=i+1;s:=s+i;
end;
时间复杂度是多少？求高手解答一下，顺便说一下为什么
答案似乎不是O(根号n）
s:=0;
while s<n do
begin i:=i+1;s:=s+i;
end;
时间复杂度是多少？求高手解答一下，顺便说一下为什么
答案似乎不是O(根号n）
先观察一下i与s的变化规律
1. i = 1, s = 1
2. i = 2, s = 3
3. i = 3, s = 6
4. i = 4, s = 10
5. i = 5, s = 15
...
不难得出s的公式
s = 1 + 2 + ...+ i = n * (n+1) / 2
所以虽然O(n)并不错， 但是更为近似和精确的结论应该是 O(根号n)，这应该是标答。
抱歉，公式打不出来。
根号n吧
不懂。难呀！