算法003-计算复杂度

以下是几个程序段的复杂度计算：
1. 程序段1：

for i in range(n):
    print(i)

该程序段的时间复杂度为O(n)，空间复杂度为O(1)。

2. 程序段2：

for i in range(n):
    for j in range(n):
        print(i, j)

该程序段的时间复杂度为O(n^2)，空间复杂度为O(1)。

3. 程序段3：

for i in range(n):
    for j in range(i):
        print(i, j)

该程序段的时间复杂度为O(n^2)，空间复杂度为O(1)。

4. 程序段4：

i = n
while i > 0:
    print(i)
    i = i // 2

该程序段的时间复杂度为O(logn)，空间复杂度为O(1)。

5. 程序段5：

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

该程序段的时间复杂度为O(2^n)，空间复杂度为O(n)。