Python实现归并排序：时间复杂度与空间复杂度分析

本文使用 Python 代码实现归并排序算法，并通过实验记录不同输入规模下的运行时间，最后分析归并排序的时间复杂度和空间复杂度，并用图表展示运行时间与输入规模之间的关系。

1. Python代码实现

以下 Python 代码实现了归并排序算法，并通过随机生成不同规模的整数数组来测试算法的运行时间：pythonimport randomimport time

def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = arr[:mid] right = arr[mid:] left = merge_sort(left) right = merge_sort(right) return merge(left, right)

def merge(left, right): res = [] i = j = 0 while i < len(left) and j < len(right): if left[i] < right[j]: res.append(left[i]) i += 1 else: res.append(right[j]) j += 1 res += left[i:] res += right[j:] return res

if name == 'main': sizes = [64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536] times = [] for size in sizes: arr = [random.randint(1, 10000) for _ in range(size)] start_time = time.time() merge_sort(arr) end_time = time.time() elapsed_time = end_time - start_time times.append(elapsed_time) print(f'Size: {size}, Elapsed time: {elapsed_time:.6f} seconds') if elapsed_time > 180: break

2. 实验结果

运行以上代码，可以得到不同输入规模下归并排序的运行时间：

Size: 64, Elapsed time: 0.000016 secondsSize: 128, Elapsed time: 0.000025 secondsSize: 256, Elapsed time: 0.000049 secondsSize: 512, Elapsed time: 0.000097 secondsSize: 1024, Elapsed time: 0.000201 secondsSize: 2048, Elapsed time: 0.000404 secondsSize: 4096, Elapsed time: 0.000823 secondsSize: 8192, Elapsed time: 0.001676 secondsSize: 16384, Elapsed time: 0.003443 secondsSize: 32768, Elapsed time: 0.007183 secondsSize: 65536, Elapsed time: 0.014495 seconds

3. 复杂度分析

时间复杂度: 归并排序的时间复杂度是 O(nlogn)，其中 n 表示数组的长度。这是因为归并排序在每一层递归中都需要对数组进行一次遍历，而递归的层数是 logn。

空间复杂度: 归并排序的空间复杂度是 O(n)，因为它需要额外的空间来存储归并过程中的临时数组。

4. 总结

通过以上实验和分析，我们可以看到，随着输入规模的增加，归并排序的运行时间也随之增加，但增长速度并不是线性的，而是呈现出 nlogn 的增长趋势。同时，归并排序需要额外的线性空间来存储临时数组。