使用Python可视化O(n)。-Python教程-PHP中文网

首页

后端开发

Python教程

使用Python可视化O(n)。

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Sep 02, 2023 pm 05:25 PM

介绍

在计算机科学和编程领域中，了解算法的效率是至关重要的，因为它有助于创建既优化又快速执行的软件。时间复杂度在这个背景下是一个重要的概念，因为它衡量了算法的运行时间随着输入规模增长的变化情况。常用的时间复杂度类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：将该元素合并到当前的总和值中。
第四步：循环结束后应返回总和。
步骤 5：结束

方法

方法1：绘制时间与输入大小的关系
方法二：绘制操作与输入规模之间的关系

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

Example

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的'n'值来评估算法，增量为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)，我们可以近似认为当绘制图表时，输入大小和执行时间之间存在几乎直线的相关性。

方法二：绘制操作与输入大小的关系

Example

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'）增长时，处理时间如何上升。