面试题：Python range函数在嵌套循环中的高级应用

Question

编写一段Python代码，使用range函数和嵌套循环创建一个二维列表。外层循环控制行数，范围是从3到7（包含3和7），内层循环控制列数，范围是从外层循环当前值的一半（向下取整）到外层循环当前值的2倍（包含）。每行的列表元素为相应的列数。请写出代码并分析代码的时间复杂度。

Answer 1

result = []
for i in range(3, 8):
    row = []
    for j in range(i // 2, 2 * i + 1):
        row.append(j)
    result.append(row)
print(result)

时间复杂度分析

1. 外层循环 for i in range(3, 8) 执行了 $8 - 3 = 5$ 次。
2. 对于每次外层循环，内层循环 for j in range(i // 2, 2 * i + 1) 执行次数为 $(2 * i + 1) - (i // 2)$ 次。
3. 总执行次数约为：
   • 当 $i = 3$ 时，内层循环执行 $(2 * 3 + 1)-(3 // 2)=7 - 1 = 6$ 次。
   • 当 $i = 4$ 时，内层循环执行 $(2 * 4 + 1)-(4 // 2)=9 - 2 = 7$ 次。
   • 当 $i = 5$ 时，内层循环执行 $(2 * 5 + 1)-(5 // 2)=11 - 2 = 9$ 次。
   • 当 $i = 6$ 时，内层循环执行 $(2 * 6 + 1)-(6 // 2)=13 - 3 = 10$ 次。
   • 当 $i = 7$ 时，内层循环执行 $(2 * 7 + 1)-(7 // 2)=15 - 3 = 12$ 次。
   • 总执行次数约为 $6 + 7+9 + 10+12 = 44$ 次。
   • 从渐近时间复杂度角度看，内层循环执行次数是关于 $i$ 的线性函数，外层循环执行常数次（5次），所以整体时间复杂度为 $O(n)$，这里 $n$ 是所有内层循环执行次数的总和，由于外层循环次数固定，时间复杂度主要由内层循环决定，内层循环总次数与 $i$ 呈线性关系，故整体为 $O(n)$。