使用 Python 可视化 O(n)

---

介绍

了解算法的效率在计算机科学和编程领域至关重要，因为它有助于创建既优化又快速运行的软件。时间复杂度在这种情况下是一个重要的概念，因为它衡量算法的运行时间随着输入规模增长而变化的方式。常用的时间复杂度类 O(n) 表示输入大小和执行时间之间存在线性关系。

定义

在计算机科学中，算法复杂度是对运行算法所需资源（例如时间和空间利用率）的评估，这取决于其输入大小。更进一步解释，它有助于我们理解算法在考虑其输入大小的情况下执行速度有多快。用于描述算法复杂度的主要符号是大 O 符号 (O(n))。

语法

for i in range(n):
   # do something

一个 `for` 循环多次运行特定的一组指令，由 0 到 `n−1` 的范围指示，并在每次迭代中对循环内的操作或一组操作执行操作。其中 'n' 代表迭代次数。

在 O(n) 时间复杂度中，随着我们增加输入大小 'n'，执行时间成比例增长。随着 'n' 的增加，迭代次数和循环完成所需的时间也将成比例增加。线性时间复杂度显示输入大小和执行时间之间存在正比例关系。

循环内的任何任务或任务序列都可以执行，而无需考虑输入大小 'n'。这里主要需要注意的是循环执行 'n' 次迭代，导致线性时间复杂度。

算法

• 步骤 1：将 sum 变量初始化为 0

• 步骤 2：遍历提供的列表中的每个元素

• 步骤 3：将元素添加到当前的 sum 值中。

• 步骤 4：循环结束后应返回 sum。

• 步骤 5：结束

方法

• 方法 1：绘制时间与输入大小的关系图

• 方法 2：绘制操作次数与输入大小的关系图

方法 1：绘制时间与输入大小的关系图

示例

import time
import matplotlib.pyplot as plt

def algo_time(n):
    sum = 0
    for i in range(n):
        sum += i
    return sum

input_sizes = []
execution_times = []

for i in range(1000, 11000, 1000):
    start_time = time.time()
    algo_time(i)
    end_time = time.time()
    input_sizes.append(i)
    execution_times.append(end_time - start_time)

plt.plot(input_sizes, execution_times)
plt.xlabel('Input Size')
plt.ylabel('Execution Time (s)')
plt.show()

输出

此代码用于测量 `algo_time()` 算法在不同输入大小下的运行时间。我们将把我们希望测试的输入大小以及它们各自的执行时间存储在这些列表中。

使用 'for' 循环迭代一系列输入大小。在这种情况下，循环将从 1000 运行到 11000 之前，每次递增 1000。更详细地说，我们计划通过将 'n' 值从 1000 更改到 10000，每次递增 1000 来评估算法。

在循环内，我们测量 `algo_time()` 函数对于每个输入大小的执行时间。为了开始跟踪时间，我们在调用函数之前使用 `time.time()`，并在函数运行完成后立即停止它。然后我们将持续时间存储在一个名为 'execution_time' 的变量中。

对于每个给定的输入大小，我们将输入值 ('n') 及其相应的执行时间添加到各自的列表 ('input_sizes' 和 'execution_times') 中。

循环完成后，我们拥有生成绘图所需的数据。'plt.plot(input_sizes, execution_times)' 使用我们收集的数据生成一个基本的线形图。x 轴显示 'input_sizes' 值，表示不同的输入大小。

'plt.xlabel()' 和 'plt.ylabel()' 最终用于标记轴，分别表示其含义，而调用 'plt.show()' 函数使我们能够呈现图表。

通过运行此代码，我们可以通过绘制的图表来可视化执行时间如何随着较大的输入大小 ('n') 而增加。假设算法的时间复杂度为 O(n)，我们可以近似认为输入大小和执行时间之间存在几乎直线的关系。

方法 2：绘制操作次数与输入大小的关系图

示例

import matplotlib.pyplot as plt

def algo_ops(n):
    ops = 0
    sum = 0
    for i in range(n):
        sum += i
        ops += 1
    ops += 1  # for the return statement
    return ops

input_sizes = []
operations = []

for i in range(1000, 11000, 1000):
    input_sizes.append(i)
    operations.append(algo_ops(i))

plt.plot(input_sizes, operations)
plt.xlabel

plt.xlabel('Input Size')
plt.ylabel('Number of Operations')
plt.show()

输出

此代码旨在分析 `algo_ops()` 算法针对不同输入大小执行的操作次数。通过使用 `algo_ops()` 函数，可以计算从零到给定输入参数 'n' 的所有数值之和的结果，同时跟踪和记录在这些计算过程中执行的每个操作。

我们首先导入 'matplotlib.pyplot' 模块，该模块允许我们创建图表等可视化效果。

接下来，我们定义 algo_ops() 函数，该函数接受输入数字 'n'。在函数内部，我们初始化两个变量：'ops' 用于计算操作次数，'sum' 用于存储数字的累加和。

这些数组将存储我们想要检查的维度及其各自的执行持续时间。

我们使用迭代循环的一种方法是在一组多个输入比例内循环。在这种情况下，循环从 1000 运行到 10000（11000 除外）。这意味着我们将评估变量 'n' 从 1000 到 10000，每次递增 100 的技术。

在循环内，我们计算所有输入大小的 `algo_time()` 程序的性能。我们在调用程序之前使用 `time.time()` 启动一个秒表，并在子程序执行结束之后立即结束它。接下来，我们将时间间隔保存在称为 'execution_period' 的变量中。

对于每个输入大小，我们将输入值 ('n') 添加到名为 'input_sizes' 的列表中。此外，我们还将相应的处理时间附加到 'execution_times' 集合中。

循环完成后，我们已经积累了制作图表所需的基本数据。语句 'plt.plot(input_sizes, execution_times)' 使用收集到的数据创建一个基本的线形图。'input_sizes' 的值显示在 x 轴上，表示不同的输入大小。'execution_times' 的值显示在垂直轴上，表示 `algo_time()` 函数针对不同的输入大小执行所花费的时间。

最后，我们通过 'plt.xlabel()' 和 'plt.ylabel()' 来标记坐标系，以演示每个轴的含义。接下来，执行 'plt.show()' 函数以呈现图表。

一旦我们执行程序，图表将向我们显示当输入的大小 ('n') 增加时处理时间是如何增加的。

结论

总之，掌握使用 Matplotlib 在 Python 中进行时间复杂度和可视化对于任何寻求创建高效和最佳软件解决方案的程序员来说都是一项宝贵的技能。了解算法在不同输入大小下的行为使我们能够解决复杂问题并构建能够及时高效地交付结果的强大应用程序。