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

https://pic2.zhimg.com/v2-0987e30ea33a36f52bbcd4da9938da70_720w.jpg?source=3af55fa1

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

什么是算法

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

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

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

小学数学课上,你是不是可以用 3+3+3 或者 3*3 来解决三个三相加这个问题,虽然算的结果都是9,但是中间我们用的方法是不一样的。

假如你今天要做一道菜,你是不是需要菜谱,菜谱上肯定会告诉你,你做这个菜需要什么材料,分几步完成,完成这道菜需要多久。

而我们今天要讲的算法,就是计算机编程界的菜谱,它就是计算机解决问题的方法。用不同的办法去解决同一个问题,结果虽然都一样,但是过程可能千差万别。

正因为计算机解决问题的方法有很多个,我们便要拿标准去衡量,到底哪些算法更好,更适合我们去使用。

时空复杂度

怎么衡量一个算法的好坏呢?

举个现实的例子:

小明和小亮去企业面试,hr要求他们用代码实现一个需求,一天之后,两个人交付了各自的代码,都能实现hr的需求。而只有小明被录用了。这是因为:

小明的代码运行一次花了50ms,内存占用5MB。

而小亮的代码运行一次要花10s,占用内存50MB。

小亮的代码虽然能够实现功能,但是运行时间和内存占用都没有小明的少,自然没有被录用。

所以我们衡量代码的好坏要从时间和空间两个角度去考虑。即:

  • 时间复杂度
  • 空间复杂度

在本文中,我们先讲解空间复杂度。

时间复杂度

我们可以将时间复杂度划分为两个小概念:

  • 基本操作次数
  • 渐进时间复杂度

基本操作次数

我们假设计算机运行一行基础代码执行一次运算。

void T0101(){
System.out.print("hello world!"); //执行一次
}

这个方法需要执行1次运算。

void T0102(int n){
for(int i = 0; i < n; i++){// 再计算for循环外层执行次数 n+1 次
System.out.print("hello world!")//先计算for循环里层执行的次数 n次
}
}

上面这个方法需要执行(n+1+n)= 2n+1 次运算。

我们把算法需要执行的运算次数用 输入大小n 的函数表示,即 T(n).

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

我们再来看几个例子:

  1. T(n) = 3n,执行次数是线性的。
void T0103(int n){
for(int i = 0; i < n; i++){ // 外层循环n次 
System.out.print("一"); //执行一次
System.out.print("二"); //执行一次
System.out.print("三"); //执行一次
}
}
  1. 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("五");//执行一次
       }
    }
    
  2. T(n) = 2 , 执行次数是常量。

void T0105(int n){
    System.out.println("一");//没有循环次数
    System.out.println("二");//只需要输出两次内容执行次数为2
}
  1. 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)
        }
    }
}

渐进时间复杂度

现在我们已经有了T(n),是否就可以分析和比较代码的运行时间了呢?不不不,n你还没确定呢。

假设A的执行次数是T(n) = 100n,算法B执行的次数是 T(n) = 5n^2 ,这辆谁大就要取决于n了。

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

维基百科的定义如下:

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

直白的讲就是,渐进复杂度就是将我们计算的程序的执行次数函数T(n) 简化为数量级,例如 nn^2n^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

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

  1. T(n) = 3n,最高阶项为3n ,省去3,则转化为的时间复杂度为:

T(n) = O(n)

O(n)

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

    T(n) = O(logn)

    O(logn)

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

    T(n) = O(1)

    O(1)

  3. 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 逐渐增大时,时间复杂度的差异性就体现出来了。

n20时,T(n)5n^2 的增长速度比T(n) = 100

比较

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

总结

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

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

AI悦创·推出辅导班啦,包括「Python 语言辅导班、C++辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。QQ、微信在线,随时响应!V:Jiabcdefh
AI悦创 » 【久远讲算法①】什么是时间复杂度

发表评论