一个图像的大体形状是由表达式的类型而非具体的表达式所确定的:
- 所有的线性表达式都会产生一条直线;
- 所有的二次表达式都会产生一条抛物线;
- 所有的对数表达式都会产生一条对数曲线。
习惯上我们用可以产生一个形状最简单的表达式来标识该形状,
具体而言,我们用表达式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()
一元二次函数(二次表达式)
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()
对数函数(对数表达式)
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()
由于通过比较一个算法执行任务所需要的事件与其输入数据大小所得的图形,可以反映该算法的效率特性,因此可以根据这些图的形状对算法进行分类——通常是基于算法的最差情况分析,用来标识这些类型的符号有时称为大$O$符号。
- 所有图形为抛物线的算法,如插入排序算法,都划归为$O$(n**2)表示的算法类型;
- 所有图形为对数曲线的算法,如二分搜索算法,都划分到$O$($log$2$N$)表示的算法类型。
知道特定算法所属的类型可以使我们可以预测它的性能,并且可以拿它与能够给解决相同问题的其他算法进行比较。两个$O$(n2)算法在输入大小增加的时候,对于事件将会有相近的需求变化。此外,$O$($log$2$N$)算法不会像$O$(n2)算法那样,随着输入大小的增加对时间的需求扩张得那么快。