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

x=n; // n>1 y=0; while(x>=(y+1)*(y+1)) y++; 算法行为解析 初始化：x = n（n > 1），y = 0。循环条件：while (x >= (y+1)*(y+1))。循环体：每次迭代中 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​)。