面试题：Python中计算列表元素平方和的时间复杂度分析

Question

请编写一个Python函数，计算给定列表中所有元素的平方和。然后分析该函数的时间复杂度，并说明在不同规模输入下的性能表现。示例列表：[1, 2, 3, 4]，函数返回应为1 + 4 + 9 + 16 = 30。

Answer 1

def sum_of_squares(lst):
    return sum([num ** 2 for num in lst])

时间复杂度分析

1. 列表推导部分：列表推导[num ** 2 for num in lst]会遍历列表中的每一个元素一次，时间复杂度为 $O(n)$，其中 $n$ 是列表的长度。
2. sum 函数部分：sum 函数也会遍历一次由列表推导生成的新列表，其时间复杂度同样为 $O(n)$。

整体函数的时间复杂度是 $O(n)$，因为在大 $O$ 表示法中，$O(n) + O(n)$ 仍然是 $O(n)$。

不同规模输入下的性能表现

1. 小规模输入：当输入列表的元素数量较少时，由于Python的解释执行特性以及函数调用开销等，函数执行时间会相对稳定且较短。
2. 大规模输入：随着输入列表长度 $n$ 的不断增大，函数执行时间会线性增长。这是因为函数的时间复杂度为 $O(n)$，即执行时间与列表中元素的数量成正比。如果列表元素数量翻倍，理论上函数执行时间也会近似翻倍。