绘制算法复杂度公式函数

cooolr 于 2021-02-23 发布

一个图像的大体形状是由表达式的类型而非具体的表达式所确定的:

习惯上我们用可以产生一个形状最简单的表达式来标识该形状,

具体而言,我们用表达式n**2来标识抛物线,用$log$2$N$来标识对竖曲线。

`

一元一次函数(线性表达式)

import numpy as np
import matplotlib.pyplot as plt

x = np.arange(0, 10, 0.1)
y = x * 2

plt.plot(x, y)

plt.show()

%E7%BB%98%E5%88%B6%E7%AE%97%E6%B3%95%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%85%AC%E5%BC%8F%E5%87%BD%E6%95%B0%20c6dd9d61f45e439688e8e47905f030f0/Figure_1.png

一元二次函数(二次表达式)

import numpy as np
import matplotlib.pyplot as plt

x = np.arange(-10, 10, 0.1)
y = x**2 + 2*x + 1

plt.plot(x, y)

plt.show()

%E7%BB%98%E5%88%B6%E7%AE%97%E6%B3%95%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%85%AC%E5%BC%8F%E5%87%BD%E6%95%B0%20c6dd9d61f45e439688e8e47905f030f0/Figure_1%201.png

对数函数(对数表达式)

import math
import numpy as np
import matplotlib.pyplot as plt

# 定义指数函数 
def log(x, a=2): 
    y=math.log(x, a)
    return y

x = np.linspace(0.01, 4, 100)
y = [log(i) for i in x]

plt.plot(x, y)

plt.show()

%E7%BB%98%E5%88%B6%E7%AE%97%E6%B3%95%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%85%AC%E5%BC%8F%E5%87%BD%E6%95%B0%20c6dd9d61f45e439688e8e47905f030f0/Figure_1%202.png

由于通过比较一个算法执行任务所需要的事件与其输入数据大小所得的图形,可以反映该算法的效率特性,因此可以根据这些图的形状对算法进行分类——通常是基于算法的最差情况分析,用来标识这些类型的符号有时称为大$O$符号。

知道特定算法所属的类型可以使我们可以预测它的性能,并且可以拿它与能够给解决相同问题的其他算法进行比较。两个$O$(n2)算法在输入大小增加的时候,对于事件将会有相近的需求变化。此外,$O$($log$2$N$)算法不会像$O$(n2)算法那样,随着输入大小的增加对时间的需求扩张得那么快。