#include <stdio.h> int sum=0; void fun(int low) { sum++; for(int i=1;i<=low/2;i++) { fun(i); } } int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int n; scanf("%d",&n); fun(n); printf("%d",sum); return 0; }用迭代法求时间复杂度

这段代码的时间复杂度可以使用迭代法求解。首先我们观察代码中的循环：

for(int i=1;i<=low/2;i++)
{
    fun(i);
}

每次循环中，`fun` 函数的参数都是 `low` 的一半。因此，如果我们假设 `T(n)` 表示 `fun(n)` 的时间复杂度，那么有：

$$
T(n) = \sum_{i=1}^{n/2} T(i)
$$

接下来我们考虑如何使用迭代法求解上述递推式。我们可以先手动计算一些小规模的情况，得到如下表格：

| n | T(n) |
| --- | ---- |
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | 8 |
| 5 | 16 |
| 6 | 32 |

通过观察上述表格，我们可以发现：

$$
T(n) = 2^{n-1}
$$

这个结论可以用数学归纳法证明，这里不再赘述。因此，这段代码的时间复杂度为 $O(2^n)$。