欢迎来到军工软件开发人才培养基地——学到牛牛

时间复杂度

时间:2024-05-06 07:01:10 来源:学到牛牛

作为刚入编程坑的小白,在做完一道题之后可能经常碰到一些大佬说你这个答案时间复杂度太高了,那这个时候可能有人就疑惑了,做题就做题时间复杂度是啥啊?今天我们就来浅谈一下时间复杂度这个概念

到底什么叫时间复杂度?以下是百度百科的官方解释:在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。

说白话一点,时间复杂度就是用来方便开发者估算出程序的运行时间,衡量一个算法好坏的重要指标

打个简单的比方,小明和小红同时去一家公司面试,做同一个编程题,小明和小红各自交付了代码,两端代码实现的功能都差不多。小红的代码运行一次要花100毫秒,内存占用5MB。小明的代码运行一次要花100秒,内存占用500MB。于是小红成功面试上这家公司。

由此可见,衡量代码的好坏,包括两个非常重要的指标:

1.运行时间;

2.占用空间;

我们该如何估计程序运行时间呢,我们通常会估计算法的操作单元数量,来代表程序消耗的时间, 这里我们默认CPU的每个单元运行消耗的时间都是相同的。

假设算法的问题规模为n,那么操作单元数量便用函数f(n)来表示,随着数据规模n的增大,算法执行时间的增长率和f(n)的增长率相同,这称作为算法的渐近时间复杂度,简称时间复杂度,记为 O(f(n)),这种表示方法叫做大O符号表示法,又称渐进符号,是用于描述函数渐进行为的数学符号。

0.png

如何推导出时间复杂度呢?有如下几个原则:

1.如果运行时间是常数量级,用常数1表示;

2.只保留时间函数中的最高阶项;

3.如果最高阶项存在,则省去最高阶项前面的系数。

我们现在比较常见的算法就是十大排序中的时间复杂度

1.png

下图中我们可以看出 不同算法的时间复杂度 在不同数据输入规模下的差异。

2.png

我们在决定使用那些算法的时候 ,不是时间复杂越低的越好,要考虑数据规模,如果数据规模很小 甚至可以用O(n^2)的算法比 O(n)的更合适

就像上图中图中 O(5n^2) 和 O(100n) 在n为20之前 很明显 O(5n^2)是更优的,所花费的时间也是最少的,这就是不同时间复杂度带来的差距。