时间戳

首页 > 解决方案 > 合并排序与线性排序：用 Python 证明时间复杂度

python - 合并排序与线性排序：用 Python 证明时间复杂度

问题描述

所以我的任务是证明合并排序的最坏情况比 Python 中具有 500,000 个值的元素的快速排序的最坏情况快多少倍。到目前为止，我已经编写了合并排序的代码，从 0 到 100 万之间的数字中随机选择，这就是我目前所拥有的。

我正要编写线性搜索的代码，直到我突然意识到我不知道如何证明每个算法的最坏情况快多少倍 - 以及我将如何证明它。

我应该怎么办？

标签： pythonsorting

解决方案

您可以使用该timeit模块：

import timeit

def merge_sort(input_list):
    ...

def linear_sort(input_list):
    ...

list_input = [50, 345, ...]

print(timeit.timeit(f"merge_sort({list_input})", setup="from __main__ import merge_sort", number=1000))

print(timeit.timeit(f"linear_sort({list_input})", setup="from __main__ import linear_sort", number=1000))

number=决定了它应该运行代码的次数。该timeit模块准确地测量运行功能所花费的时间。需要设置代码来导入timeit模块使用的功能，并且不包含在运行时间中。

如果您需要生成 500k 个元素的列表，类似这样的方法可能会起作用：

import random

list_input = [random.randint(0, 1000000) for _ in range(500000)]

您可以进一步将timeit代码包含在一个while或for循环中，并取几次运行的平均值。

for _ in range(10):
    merge_time += timeit.timeit(...)
    linear_time += timeit.timeit(...)

merge_avg = merge_time / 10
linear_avg = linear_time / 10

print(f"Merge Sort was {merge_avg/linear_avg}x faster than Linear Sort")

推荐阅读