什么是算法
今天先讨论一个问题吧。 算法是什么？算法是指计算方法吗？ 不准确。
算法这个名称听起来很硬核，但换个场景我就很熟悉了。
在小学数学课上，你能用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 快
可见当我们要处理的对象足够大的时候，选时间复杂度较低的算法可使我们事半功倍，提高我们的程序运行效率。
总结
本次我们详细的介绍了时间复杂度的概念。下次我们将引入空间复杂度的概念。
点击关注作者不迷路，持续更新数据结构讲解以及力扣刷题技巧。