学习算法应该首先了解怎么去评估一个算法的好坏以及怎么去计算一个算法的效率,只有知道了这个,才能够写出好的算法
1、下面了解一些基本概念:
- 函数渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么可以说f(n)的渐近快于g(n)
- 算法的时间复杂度:在进行算法分析的时候,总的执行次数T(n)是关于问题规模n的一个函数,分析T(n)随n的变化情况来确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)= O(f(n)),表示随着问题规模n的扩大,算法执行的时间增长率和f(n)的增长率相同,称为算法的渐近时间复杂度,简称时间复杂度,其中f(n)表示关于问题规模n的某个函数。
- O():规定使用O()来表示算法的时间复杂度,称之为大O记法
2、了解了基本基本概念之后,就来学习下怎么进行大O的推导吧
推导大O分为三个部分
1. 使用常数1取代f(n)中所有加法常数
2. 只保留最高项阶
3. 如果最高项阶存在同时系数不是1,那么去掉这个系数