什么是算法
今天先讨论一个问题吧。 算法是什么?算法是指计算方法吗? 不准确。
算法这个名称听起来很硬核,但换个场景我就很熟悉了。
在小学数学课上,你能用33或3*3解三加这个题吗? 虽然计算结果都是9,但是中途我们使用的方法不同。
如果你今天做饭,你会告诉我是否需要菜谱,菜谱上一定要你做这道菜需要什么材料,分几步完成这道菜需要多长时间。
我们今天要讲的算法是计算机编程界的食谱,那就是计算机解决问题的方法。 即使用不同的方法解决同样的问题,结果也是一样的,但过程可能千差万别。
由于计算机有很多解决问题的方法,我们必须有标准地进行测量。 哪个算法更好,适合我们使用吗?
时空复杂度
算法的好坏怎么衡量呢?举个现实的例子:
紧凑型菠萝和yldmz去企业面试,hr要求通过代码实现一个需求。 一天后,两人交付了各自的代码,实现了hr的需求。 只有紧凑的菠萝被采用了。 这是:
紧凑的菠萝代码一次需要50ms,内存消耗5MB。
另一方面,yldmz的代码一次需要10s,消耗50MB的内存。
yldmz的代码虽然实现了功能,但是运行时和内存占用空间都不及紧凑的菠萝,当然没有被采用。
所以我们必须从时间和空间两个角度来考虑代码的好坏。 也就是说:
时间复杂度空间复杂度本文首先说明空间复杂度。
时间复杂度
小时的复杂性可以分为两个小概念:假设基本操作次数渐进时间复杂度
基本操作次数
计算机执行一行基本代码执行一次运算。void T0101 ()
system.out.print('Helloworld!' ); //执行一次
}
这个方法需要一次运算。
voidt 0102 (国际) {
for (英制=0; i n; I )//重新计算for循环外层执行次数n 1次
system.out.print('Helloworld!' //for循环内的层被执行的次数先计算n次
}
{1}上述方法需要(n 1 n )=2n 1次的运算。
用输入大小n的函数,即t(n )来表示算法应该执行的运算次数。
为了估算算法所需的执行时间,简化算法分析,引入了时间复杂度的概念。
让我们来看几个例子:
1.T(n)=3n,执行次数是线性的。
语音0103 (Intn ) {for (英制=0; i n; I () /外层循环n次
系统输出打印(一); //执行一次
系统输出打印(二); //执行一次
System.out.print ('三'; //执行一次
}
}
2.T(n) = 5lognT(n)=5logn ,执行次数是用对数计算的。
语音0104 (英寸) {for (英寸=n; i1; 观察i/=2)//n和I的运算关系为对数关系
系统输出('一); //执行一次
系统输出(二); //执行一次
系统输出('三); //执行一次
系统输出打印(四); //执行一次
系统出口打印(五); //执行一次
}
}
3.T(n)=2 , 执行次数是常量。
语音0105 (Intn ) {系统输出('一); //没有循环次数
系统输出(二);//输出2次即可内容的执行次数为2次
4.T(n)=n2 ,执行次数为幂函数。
语音0106 (国际) )for (英制=0; i n; I )//循环数为n
for(intj=0; j-n; j ()//循环次数为n
system.out.println('Hello,World!' ); //循环体的时间复杂度为o(1)
}
}
}
渐进时间复杂度
现在我们有t(n ),能分析和比较代码的执行时间吗? 不,不,n还没有确定。如果设a的执行次数为t(n )=100n )=100n,算法b的执行次数为t ) n )=5n2t(n )=5n2,则该谁较大取决于n。
>因此为了解决这类难题,我们有了渐进时间复杂度的概念。维基百科的定义如下:
在计算机科学中,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。
直白的讲就是,渐进复杂度就是将我们计算的程序的执行次数函数T(n)T(n)T(n) 简化为数量级,例如 nnn、n2n^2n2 、n3n^3n3 等。
那我们要如何推算出时间复杂度呢?有以下几个原则:
如果运行时间是常数级的(例如:1,2,3,4,6等),则直接用常数1代替表示。只保留时间函数中的最高阶项。如果最高阶项存在,则省去最高阶项前面的系数。例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3+3n5n^3 + 3n5n3+3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3)O(n^3)O(n3)。
这个推算过程即为:
1.保留函数中的最高阶项。
即: 5n3+3n5n^3+3n5n3+3n −>->−> 5n35n^35n3
2.最高阶项存在,则省去最高阶项前面的系数。
即: 5n35n^35n3 −>->−> n3n^3n3
我们再来复习一下我们刚才看的那几个计算时间函数的例子。
T(n)=3nT(n) = 3nT(n)=3n最高阶项为3n3n3n ,省去3,则转化为的时间复杂度为:
T(n)=O(n)T(n) = O(n)T(n)=O(n)
2.T(n) = 5lognT(n)=5logn , 最高阶项为 5logn5logn,省去系数 5,则转化的时间复杂度为:
T(n) = O(logn)T(n)=O(logn)
3.T(n) = 2T(n)=2,只有常数量级,则拿1替换常数,转换后的时间复杂度为:
T(n) = O(1)T(n)=O(1)
4.T(n)=n^2T(n)=n2
这四种时间复杂度究竟谁更快,谁更更慢呢?当n足够大时,我们可以得到这样的结论:
O(1)<O(logn)<O(n)<O(n2)O(1)<O(logn)<O(n)<O(n^2)O(1)<O(logn)<O(n)<O(n2)时间复杂度的差异
介绍了这么多,肯定有读者心中会产生疑问,你这说了半天...函数式子,能不能让我们直接体会一下时间复杂度的差异?
假设算法A的执行次数是T(n)=100nT(n) =100nT(n)=100n ,
时间复杂度为O(n)=nO(n)=nO(n)=n
算法B的执行次数是T(n)=5n2T(n) = 5n^2T(n)=5n2 ,
时间复杂度为O(n)=n2O(n) = n^2O(n)=n2
如果 n=1n=1n=1,使用算法A和算法B的次数均为1
但是当nnn 逐渐增大时,时间复杂度的差异性就体现出来了。
当n<20n<20n<20时,T(n)=100nT(n)=100nT(n)=100n的增长速度比T(n)=5n2T(n)=5n^2T(n)=5n2快
当n>20n>20n>20时,T(n)5n2T(n)5n^2T(n)5n2 的增长速度比T(n)=100T(n) = 100T(n)=100 快
可见当我们要处理的对象足够大的时候,选时间复杂度较低的算法可使我们事半功倍,提高我们的程序运行效率。
总结
本次我们详细的介绍了时间复杂度的概念。下次我们将引入空间复杂度的概念。
点击关注作者不迷路,持续更新数据结构讲解以及力扣刷题技巧。