【久远讲算法①】什么是时间复杂度

AI悦创

共 2964字,需浏览 6分钟

 ·

2021-10-10 01:43

阅读本文大概需要6分钟

你好,我是久远,今天开始,由我来给大家分享算法以及数据结构的相关知识。

什么是算法


今天我们先来讨论一个问题:什么是算法?


算法是指计算方法么?并不准确。


算法这个名称虽然听着硬核,但是我们换个场景你就会非常熟悉。


小学数学课上,你是不是可以用 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).


为了估算算法需要的运行时间和简化算法分析,我们引入时间复杂度的概念。


我们再来看几个例子:


  1. ,执行次数是线性的。
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. ,执行次数是用对数计算的。

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. , 执行次数是常量。

void T0105(int n){
System.out.println("一");//没有循环次数
System.out.println("二");//只需要输出两次内容执行次数为2
}
print("一")#无循环次数
print("二")#只需要输出两次内容执行的次数为2
  1. ,执行次数为幂函数。
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的执行次数是,算法B执行的次数是  ,这俩谁大就要取决于n了。


因此为了解决这类难题,我们有了渐进时间复杂度的概念。


维基百科的定义如下:

在计算机科学中,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。
维基百科

直白的讲就是,渐进复杂度就是将我们计算的程序的执行次数函数 简化为数量级,例如  、 等。


那我们要如何推算出时间复杂度呢?有以下几个原则:


  • 如果运行时间是常数级的(例如:1,2,3,4,6等),则直接用常数1代替表示。
  • 只保留时间函数中的最高阶项。
  • 如果最高阶项存在,则省去最高阶项前面的系数。

例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要  的时间运行完毕,那么它的渐近时间复杂度是 


这个推算过程即为:


  • 保留函数中的最高阶项。

即:   


  • 最高阶项存在,则省去最高阶项前面的系数。

即:   


我们再来复习一下我们刚才看的那几个计算时间函数的例子。



最高阶项为 ,省去3,则转化为的时间复杂度为:


O(n)
  1. , 最高阶项为 ,省去系数 5,则转化的时间复杂度为:

O(logn)
  1. ,只有常数量级,则拿1替换常数,转换后的时间复杂度为:


    O(1)




这四种时间复杂度究竟谁更快,谁更更慢呢?


当 n 足够大时,我们可以得到这样的结论:


<<<


时间复杂度比较

时间复杂度的差异

介绍了这么多,肯定有读者心中会产生疑问,你这说了半天...函数式子,能不能让我们直接体会一下时间复杂度的差异?


假设算法A的执行次数是  ,

时间复杂度为 

 

算法B的执行次数是   ,

时间复杂度为 


如果 ,使用算法A和算法B的次数均为1

但是当 逐渐增大时,时间复杂度的差异性就体现出来了。


当 时,的增长速度比

当 时, 的增长速度比

比较


可见当我们要处理的对象足够大的时候,选时间复杂度较低的算法可使我们事半功倍,提高我们的程序运行效率。

总结

本次我们详细的介绍了时间复杂度的概念。下次我们将引入空间复杂度的概念。

点个公众号关注不迷路。持续更新数据结构讲解以及力扣刷题技巧。

长按识别下方二维码,和众多位岛民一起

把别人的顿悟,变成你的基本功


 花半秒钟就看透事物本质的人,
  和花一辈子都看不清的人,
  注定是截然不同的命运。

浏览 25
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报