例题：求算法的时间复杂度

x=n; // n>1
y=0;
while(x>=(y+1)*(y+1))
y++;

算法行为解析

1. 初始化：x = n（n > 1），y = 0。
2. 循环条件：while (x >= (y+1)*(y+1))。
3. 循环体：每次迭代中 y 递增 1。

目标：找到最大的整数 y，使得 (y+1)2≤n(y+1)2≤n。

---

循环次数分析

• 终止条件：当 (y+1)2>n(y+1)2>n 时，循环结束。
• 最终 y 的值：满足 y≤n−1<y+1y≤n​−1<y+1，即 y=⌊n⌋y=⌊n​⌋。
• 循环次数：等于最终的 y 值，即循环执行了 ⌊n⌋⌊n​⌋ 次。

举例：

• 若 n=16n=16，则 ⌊16⌋=4⌊16​⌋=4，循环执行 4 次。
• 若 n=15n=15，则 ⌊15⌋=3⌊15​⌋=3，循环执行 3 次。

---

时间复杂度推导

• 每次循环操作（条件判断和 y++）的时间复杂度为 O(1)O(1)。
• 总循环次数为 ⌊n⌋⌊n​⌋，与 nn​ 同阶。
• 因此，时间复杂度为 O(n)O(n​)。

---

数学严谨性验证

设循环次数为 kk，则结束时满足：
k2≤n<(k+1)2k2≤n<(k+1)2
解得 k=⌊n⌋k=⌊n​⌋，故时间复杂度严格为 Θ(n)Θ(n​)。

---

结论

算法的时间复杂度为 O(n)O(n​)，精确表示为 Θ(n)Θ(n​)。