O(n)
-
时间换空间
空间复杂度分析
S(n)
-
空间换时间
递归算法的时间复杂度
递归算法的时间复杂度取决于：递归的次数 * 每次递归中的操作次数。
题目：求 x 的 n 次方
方法一：
-
时间复杂度 O(n)
def function1(x, n):
result = 1
for i in range(n):
result *= x
return result方法二：
-
时间复杂度 O(n)
x^5 = 1*x*x*x*x*x 计算 5 次
def function2(x, n):
if n == 0:
return 1
else:
return function2(x, n-1) * x方法三：
-
时间复杂度：O(logn)
x^4 = x^2 * x^2 = x*x * x*x 计算 2 次 x^5 = x^2 * x^2 * x 计算 2 次
def function3(x, n):
if n == 0: return 1
if n == 1: return x
// 空间换时间, 不管 n 为奇数还是偶数，t 值一样
t = function3(x, n/2)
// 如果 n 为奇数，多乘以个 x 返回
if n%2 == 1: return t*t*x
// 如果 n 为偶数，直接返回 t 值
return t * t正文完
