使用 Python 可视化 O（n）

很酷的站长

发布于 2023-08-11 15:37:07

1910

发布于 2023-08-11 15:37:07

介绍

了解算法的效率在计算机科学和编程领域至关重要，因为它有助于创建既优化又性能快速的软件。在这种情况下，时间复杂度是一个重要的概念，因为它衡量算法的运行时如何随着输入大小的增长而变化。常用的时间复杂度类 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 步：将元素合并到当前总和值中。
步骤4：完成循环后应返回总和。
第 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 的步长递增。为了进一步详细说明，我们计划通过以 1000 为增量从 10000 到 1000 的“n”值来评估算法。

在循环中，我们测量每个输入大小的 'algo_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'）增长时，处理时间是如何增加的。