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()

输出

Python 可视化O(n)

这段代码用于测量algo_time()算法在不同输入大小下的运行时间。我们将存储要测试的输入大小及其相应的执行时间在这些列表中。

使用for循环来迭代一系列的输入大小。在这种情况下，循环将从1000开始，直到接近11000之前，每次增加1000。具体来说，我们打算通过从1000到10000的n值进行测试。

在循环中，我们测量每个输入大小下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()

输出

Python 可视化O(n)

这段代码旨在分析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’）增大时，处理时间如何增加。