01-【久远讲算法】什么是时间复杂度
大家好 ，我是久远，今天开始，由我来给大家分享算法以及数据结构的相关知识。
什么是算法
今天我们先来讨论一个问题：什么是算法？
算法是指计算方法么？并不准确。
算法这个名称虽然听着硬核，但是我们换个场景你就会非常熟悉。
小学数学课上，你是不是可以用 3+3+3 或者 3*3 来解决三个三相加这个问题，虽然算的结果都是9，但是中间我们用的方法是不一样的。
假如你今天要做一道菜，你是不是需要菜谱，菜谱上肯定会告诉你，你做这个菜需要什么材料，分几步完成，完成这道菜需要多久。
而我们今天要讲的算法，就是计算机编程界的菜谱，它就是计算机解决问题的方法。用不同的办法去解决同一个问题，结果虽然都一样，但是过程可能千差万别。
正因为计算机解决问题的方法有很多个，我们便要拿标准去衡量，到底哪些算法更好，更适合我们去使用。
时空复杂度
怎么衡量一个算法的好坏呢？
举个现实的例子：
小明和小亮去企业面试，hr要求他们用代码实现一个需求，一天之后，两个人交付了各自的代码，都能实现hr的需求。而只有小明被录用了。这是因为：
小明的代码运行一次花了50ms,内存占用5MB。
而小亮的代码运行一次要花10s，占用内存50MB。
小亮的代码虽然能够实现功能，但是运行时间和内存占用都没有小明的少，自然没有被录用。
所以我们衡量代码的好坏要从时间和空间两个角度去考虑。即：
- 时间复杂度
- 空间复杂度
在本文中，我们先讲解空间复杂度。
时间复杂度
我们可以将时间复杂度划分为两个小概念：
- 基本操作次数
- 渐进时间复杂度
基本操作次数
我们假设计算机运行一行基础代码执行一次运算。
void T0101(){
System.out.print("hello world!"); //执行一次
}
print("helo world")#执行一次
这个方法需要执行1次运算。
void T0102(int n){
for(int i = 0; i < n; i++){// 再计算for循环外层执行次数 n+1 次
System.out.print("hello world!")//先计算for循环里层执行的次数 n次
}
}
for i in range(n): #再计算for循环外层执行次数 n+1 次
print("hello world!")#先计算for循环里层执行的次数为 n次
上面这个方法需要执行（n+1+n）= 2n+1 次运算。
我们把算法需要执行的运算次数用 输入大小n 的函数表示，即 T(n).
为了估算算法需要的运行时间和简化算法分析，我们引入时间复杂度的概念。
我们再来看几个例子：
- $T(n) = 3n$,执行次数是线性的。
void T0103(int n){
for(int i = 0; i < n; i++){ // 外层循环n次
System.out.print("一"); //执行一次
System.out.print("二"); //执行一次
System.out.print("三"); //执行一次
}
}
for i in range(n):# 外层循环n次
print("-")#执行一次
print("二")#执行一次
print("三")#执行一次
2.$T(n) = 5logn$ ,执行次数是用对数计算的。
void T0104(int n){
for(int i = n; i>1; i/=2){//观察n与i的运算关系 成对数关系
System.out.println("一");//执行一次
System.out.println("二");//执行一次
System.out.println("三");//执行一次
System.out.println("四");//执行一次
System.out.println("五");//执行一次
}
}
i = n #在这里n代表的是某个特定的数字，如果要进行代码复制，请将n改为指定的数字去运行
while i > 1 :
print("一")#执行一次
print("二")#执行一次
print("三")#执行一次
print("四")#执行一次
print("五")#执行一次
i = i//2
3.$T(n) = 2$ , 执行次数是常量。
void T0105(int n){ System.out.println("一");//没有循环次数 System.out.println("二");//只需要输出两次内容执行次数为2}
print("一")#无循环次数print("二")#只需要输出两次内容执行的次数为2
- $ T(n) = n^2$ ,执行次数为幂函数。
void T0106(int n) { for(int i = 0; i < n; i++) { // 循环次数为 n for(int j = 0; j < n; j++) {// 循环次数为 n System.out.println("Hello, World!"); //循环体时间复杂度为 O(1) } }}
for i in range(n):#循环次数n for j in range(n):#循环次数n print("hello world")#循环体时间复杂度为O(1)
渐进时间复杂度
现在我们已经有了T(n),是否就可以分析和比较代码的运行时间了呢？不不不，n你还没确定呢。
假设A的执行次数是$ T(n) = 100n $，算法B执行的次数是 $ T(n) = 5n^2 $ ,这辆谁大就要取决于n了。
因此为了解决这类难题，我们有了渐进时间复杂度的概念。
维基百科的定义如下：
在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
直白的讲就是，渐进复杂度就是将我们计算的程序的执行次数函数$T(n)$ 简化为数量级，例如 $n$、$n^2$ 、$n^3$ 等。
那我们要如何推算出时间复杂度呢？有以下几个原则：
- 如果运行时间是常数级的（例如：1,2,3,4,6等），则直接用常数1代替表示。
- 只保留时间函数中的最高阶项。
- 如果最高阶项存在，则省去最高阶项前面的系数。
例如，如果一个算法对于任何大小为 n （必须比 n0 大）的输入，它至多需要 $5n^3 + 3n$ 的时间运行完毕，那么它的渐近时间复杂度是 $O(n^3)$。
这个推算过程即为：
1.保留函数中的最高阶项。
即: $5n^3+3n$ $->$ $5n^3$
2.最高阶项存在，则省去最高阶项前面的系数。
即: $5n^3$ $->$ $n^3$
我们再来复习一下我们刚才看的那几个计算时间函数的例子。
- $T(n) = 3n$
最高阶项为$3n$ ,省去3，则转化为的时间复杂度为：
$$T(n) = O(n)$$
$T(n) = 5logn$ , 最高阶项为 $5logn$，省去系数 5，则转化的时间复杂度为：
$$T(n) = O(logn)$$
$T(n) = 2$，只有常数量级，则拿1替换常数，转换后的时间复杂度为：
$$T(n) = O(1)$$
- $T(n)=n^2$
这四种时间复杂度究竟谁更快，谁更更慢呢？当n足够大时，我们可以得到这样的结论：
$$O(1)<O(logn)<O(n)<O(n^2)$$
时间复杂度的差异
介绍了这么多，肯定有读者心中会产生疑问，你这说了半天...函数式子，能不能让我们直接体会一下时间复杂度的差异？
假设算法A的执行次数是$T(n) =100n$ ,
时间复杂度为$O(n)=n$
算法B的执行次数是$T(n) = 5n^2$ ,
时间复杂度为$O(n) = n^2$
如果 $n=1$，使用算法A和算法B的次数均为1
但是当$n$ 逐渐增大时，时间复杂度的差异性就体现出来了。
当$n<20$时，$T(n)=100n$的增长速度比$T(n)=5n^2$快
当$n>20$时，$T(n)5n^2$ 的增长速度比$T(n) = 100$ 快
可见当我们要处理的对象足够大的时候，选时间复杂度较低的算法可使我们事半功倍，提高我们的程序运行效率。
总结
本次我们详细的介绍了时间复杂度的概念。下次我们将引入空间复杂度的概念。
点个公众号关注不迷路。持续更新数据结构讲解以及力扣刷题技巧。