时间复杂度 浇浇我吧w

Question

Wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww

Answer 1

晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

对于给定的函数int func(int n) { int i = 0, sum = 0; while (sum < n) sum += ++i; return i; }，我们分析其时间复杂度。

在函数中，有一个while循环，循环的条件是sum < n，每次循环累加sum=sum+ ++i，直到sum大于等于n。

首先，我们来看每次sum的值变化情况：

第一次循环：sum = 1

第二次循环：sum = 3

第三次循环：sum = 6

第四次循环：sum = 10

...

可以观察到，每次循环后，sum的值是递增的等差数列，其公差为1。我们可以根据等差数列的求和公式来计算循环次数。

设循环次数为x，则有1 + 2 + 3 + ... + x = sum。根据等差数列求和公式，我们可以得到：

(1 + x) * x / 2 = sum，即x * (x + 1) / 2 = sum

由此，可以得到以下关系式：

x^2 + x - 2 * sum = 0

利用一元二次方程求根公式，可以求得x的解为x = (-1 + sqrt(1 + 8*sum)) / 2。

在函数中，循环次数x即为i的值，所以最后返回的结果为i = x。因此，循环的次数与n的大小有关。

综上所述，该函数的时间复杂度为O(sqrt(n))。