递归算法的时间复杂度分析是理解算法效率的重要步骤，尤其是在处理分治、动态规划等问题时。以下是一些基本概念和步骤，帮助你理解和分析递归算法的时间复杂度。

基本步骤

1. 确定递归关系式（Recurrence Relation）：首先需要找出递归调用的次数以及每次调用中执行了多少工作。这通常表现为一个数学公式或方程。

2. 求解递归关系式：通过代数方法或者已知模式来求解这个方程。常见的方法包括主定理（Master Theorem）、替换法（Substitution Method）、递归树（Recursion Tree Method）等。

3. 考虑边界条件：确保你的分析也适用于递归的基础情况，即最小输入规模的情况。

分析方法

1. 主定理（Master Theorem）

适用于形如 (T(n) = aT(\frac{n}{b}) + f(n)) 的递归关系式，其中：

• (a \geq 1) 和 (b > 1) 是常数，
• (f(n)) 是非递归部分的工作量。

根据 (f(n)) 相对于 (n^{\log_b{a}}) 的增长速度，可以快速得出时间复杂度：

• 如果 (f(n) = O(n^c))，其中 (c < \log_b{a})，则 (T(n) = \Theta(n^{\log_b{a}}))。
• 如果存在 (k \geq 0) 使得 (f(n) = \Theta(n^{\log_b{a}} \log^k n))，则 (T(n) = \Theta(n^{\log_b{a}} \log^{k+1} n))。
• 如果 (f(n) = \Omega(n^c))，其中 (c > \log_b{a})，且满足正则条件，则 (T(n) = \Theta(f(n)))。

示例

对于二分查找算法，其递归关系为 (T(n) = T(\frac{n}{2}) + O(1))，应用主定理可得时间复杂度为 (O(\log n))。

2. 替换法（Substitution Method）

猜测递归式的解，然后使用数学归纳法证明该猜测正确。此方法灵活性大但需一定的直觉。

示例

假设我们猜测归并排序的时间复杂度为 (O(n \log n))，可以通过归纳法验证这一猜测是否成立。

3. 递归树（Recursion Tree Method）

将递归过程可视化为一棵树，每个节点表示一层递归调用的成本。通过计算树的所有层成本之和来估计总成本。

示例

对于归并排序，每一层递归都将问题分为两半，并且每层的合并操作花费线性时间。因此，递归树的高度为 (O(\log n))，每层的成本为 (O(n))，从而总成本为 (O(n \log n))。

实际例子分析

例子1: 斐波那契数列（朴素递归）

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

• 每次递归调用会生成两个新的递归调用。
• 时间复杂度为 (O(2^n))，因为每增加一次递归深度，函数调用的数量几乎翻倍。

例子2: 快速排序

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    less = [x for x in arr[1:] if x < pivot]
    greater = [x for x in arr[1:] if x >= pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

• 在最坏情况下（已经排序的数组），每次选择的第一个元素作为基准点会导致不平衡分割，时间复杂度为 (O(n^2))。
• 平均情况下，快速排序的时间复杂度为 (O(n \log n))。

通过这些方法，你可以更好地理解和预测递归算法的性能特性，从而优化算法设计。

在Python中，测量代码的实际执行时间是一个常见的需求，尤其是在性能优化或算法分析时。以下是几种常用的方法，从简单到高级逐步介绍。

---

1. 使用 time 模块

time 模块提供了高精度的时间测量工具，适合测量短时间范围的代码执行时间。

示例代码：

import time

start_time = time.time()  # 获取当前时间戳（秒）
# 需要测量的代码
for i in range(1000000):
    pass
end_time = time.time()

execution_time = end_time - start_time
print(f"代码执行时间：{execution_time:.6f} 秒")

特点：

• 精度较高，单位为秒。
• 适合测量较长时间的代码段。

---

2. 使用 timeit 模块

timeit 是 Python 内置的一个专门用于测量小段代码执行时间的模块，能够避免垃圾回收、系统调用等干扰因素的影响。

示例代码：

import timeit

# 定义需要测试的代码
code_to_test = """
for i in range(1000000):
    pass
"""

# 测量执行时间，默认运行100万次
execution_time = timeit.timeit(code_to_test, number=1000)
print(f"代码执行时间：{execution_time:.6f} 秒")

特点：

• 更加精确，尤其适合测量短时间的代码段。
• 支持多次运行以减少偶然误差。
• 自动禁用垃圾回收器，确保测量结果更准确。

---

3. 使用 datetime 模块

datetime 模块可以记录时间点，适合粗略测量较长代码段的执行时间。

示例代码：

from datetime import datetime

start_time = datetime.now()  # 获取当前时间
# 需要测量的代码
for i in range(1000000):
    pass
end_time = datetime.now()

execution_time = end_time - start_time
print(f"代码执行时间：{execution_time}")

特点：

• 时间格式直观，便于阅读。
• 精度较低，适合测量较长时间的代码段。

---

4. 使用 perf_counter 或 process_time

time 模块中的 perf_counter 和 process_time 提供了更高精度的时间测量工具。

示例代码：

import time

# 使用 perf_counter（高精度计时器）
start_time = time.perf_counter()
# 需要测量的代码
for i in range(1000000):
    pass
end_time = time.perf_counter()

execution_time = end_time - start_time
print(f"代码执行时间（perf_counter）：{execution_time:.6f} 秒")

# 使用 process_time（仅统计CPU时间）
start_time = time.process_time()
# 需要测量的代码
for i in range(1000000):
    pass
end_time = time.process_time()

execution_time = end_time - start_time
print(f"代码执行时间（process_time）：{execution_time:.6f} 秒")

区别：

• perf_counter：测量墙上时间（wall-clock time），包括睡眠时间。
• process_time：测量CPU时间，不包括等待I/O或其他线程的时间。

特点：

• 精度极高，适合测量微秒级或纳秒级的代码段。
• process_time 更适合分析CPU密集型任务。

---

5. 使用第三方库 line_profiler

如果需要逐行分析代码的执行时间，可以使用 line_profiler 库。

安装：

pip install line_profiler

示例代码：

@profile
def my_function():
    total = 0
    for i in range(1000000):
        total += i
    return total

if __name__ == "__main__":
    my_function()

运行：

在命令行中运行以下命令：

kernprof -l -v script.py

特点：

• 可逐行显示代码的执行时间。
• 非常适合定位性能瓶颈。

---

6. 使用 cProfile 分析性能

cProfile 是 Python 内置的性能分析工具，可以生成详细的性能报告。

示例代码：

import cProfile

def my_function():
    total = 0
    for i in range(1000000):
        total += i
    return total

cProfile.run('my_function()')

输出示例：

         5 function calls in 0.031 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.031    0.031    0.031    0.031 <string>:1(<module>)
        1    0.000    0.000    0.031    0.031 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

特点：

• 提供详细的函数调用次数和执行时间。
• 适合分析复杂的程序性能。

---

总结：如何选择方法？

方法	精度	适用场景
time 模块	较高	快速测量一般代码段的执行时间
timeit 模块	高	测量短时间的代码段，排除干扰因素
datetime 模块	中	测量较长时间的代码段
perf_counter	极高	测量微秒级或纳秒级的代码段
process_time		测量CPU时间
line_profiler		逐行分析代码性能
cProfile	高	复杂程序的整体性能分析

根据实际需求选择合适的方法，快速定位性能问题并优化代码！

n = 100
for i in range(n):
    print("hello")
    
for i in range(n):
    print("hello")

n = 5
if n%2 == 0:
    print("偶数")
else:
    print("奇数")

n = 5

for i in range(1,n+1):
    for j in range(1,n+1):
        print("*",end="")#基本执行语句
    print()