计算复杂度和时间复杂度（计算复杂度和时间复杂度的公式）

大家好！今天让创意岭的小编来大家介绍下关于计算复杂度和时间复杂度的问题，以下是小编对此问题的归纳整理，让我们一起来看看吧。

开始之前先推荐一个非常厉害的Ai人工智能工具，一键生成原创文章、方案、文案、工作计划、工作报告、论文、代码、作文、做题和对话答疑等等

只需要输入关键词，就能返回你想要的内容，越精准，写出的就越详细，有微信小程序端、在线网页版、PC客户端

官网：https://ai.de1919.com。

创意岭作为行业内优秀的企业，服务客户遍布全球各地，如需了解SEO相关业务请拨打电话175-8598-2043，或添加微信：1454722008

本文目录:

• 1、时间复杂度怎么算

• 2、时间复杂度怎么算

• 3、一文讲透算法中的时间复杂度和空间复杂度计算方式

• 4、究竟什么是时间复杂度，怎么求时间复杂度，看这一篇就够了

一、时间复杂度怎么算

问题一：请问算法的时间复杂度是怎么计算出来的? 首先假设任意一个简单运算的时间都是1，例如a=1;a++;a=a*b;这些运算的时间都是1.

那么例如

for(int i=0;i 问题二：数据结构中的时间复杂度怎么算啊？看不懂啊，有没有具体的公式 求时间复杂度，其实是在统计基本操作步骤的执行次数。

“基本操作步骤”指的是加减乘除这种。比如有一个for循环，执行N次，每次做一个加法一个乘法，那么总的操作步骤数就是2N，用大O记号就是O(N).

原理就是这么简单，计数而已。

实际做题的时候，看清楚for循环的嵌套层数，就差不离。

问题三：如何计算算法的时间复杂度 求解算法的时间复杂度的具体步骤是：⑴找出算法中的基本语句；算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。⑵计算基本语句的执行次数的数量级；只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。⑶用大Ο记号表示算法的时间性能。将基本语句执行次数的数量级放入大Ο记号中。如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：for(i=1;i 问题四：如何计算时间复杂度 如何计算时间复杂度

定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数 T(n)称为这一算法的“时间复杂性”。

当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。

此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。

“大 O记法”：在这种描述中使用的基本参数是 n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。

O(1)

Temp=i;i=j;j=temp;

以 上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时 间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n^2)

2.1. 交换i和j的内容

sum=0； （一次）

for(i=1;i>

问题五：时间复杂度如何计算 10分 给我十分，我告诉你答案

问题六：C语言算法的时间复杂度如何计算啊？ 看看这个 每个循环都和上一层循环的参数有关。 所以要用地推公式： 设i(n)表示第一层循环的i为n时的循环次数，注意到他的下一层循环次数刚好就是n，分别是0,1,2...n-1 所以，把每一层循环设一个函数分别为：j(n),k(n),t(n) 则有 i(n)=j(0)+...+j(n-1) j(n)=k(0)+...+k(n-1) k(n)=t(0)+...+t(n-1) i(0)=j(0)=k(0)=0 t(n)=1 而总循环数是i(0)+i(1)...+i(n-1) 可以根据递推条件得出准确值 所以算法复杂度是O(i(0)+i(1)...+i(n-1))

记得采纳啊

问题七：程序中的时间复杂度是怎么计算的？ 算法复杂度的介绍，见百科：

baike.baidu/view/7527

时间复杂度

时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

计算方法

1. 一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n））

分析：随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。

2. 在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））

例：算法：

for（i=1;i>

问题八：人脸识别的计算时间复杂度怎么算 递归算法的时间复杂度分析 收藏 在算法分析中，当一个算法中包含递归调用时，其时间复杂度的分析会转化为一个递归方程求解。实际上，这个问题是数学上求解渐近阶的问题，而递归方程的形式多种多样，其求解方法也是不一而足，比较常用的有以下四种方法： (1)代入法(Substitution Method) 代入法的基本步骤是先推测递归方程的显式解，然后用数学归纳法来验证该解是否合理。 (2)迭代法(Iteration Method) 迭代法的基本步骤是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计。 (3)套用公式法(Master Method) 这个方法针对形如“T(n) = aT(n/b) + f(n)”的递归方程。这种递归方程是分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子问题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。 (4)差分方程法(Difference Formula Method) 可以将某些递归方程看成差分方程，通过解差分方程的方法来解递归方程，然后对解作出渐近阶估计。 下面就以上方法给出一些例子说明。 一、代入法 大整数乘法计算时间的递归方程为：T(n) = 4T(n/2) + O(n)，其中T(1) = O(1)，我们猜测一个解T(n) = O(n2 )，根据符号O的定义，对n>n0，有T(n) >

问题九：如何计算算法的时间复杂度和空间复杂度 是说明一个程序根据其数据n的规模大小 所使用的大致时间和空间

说白了 就是表示 如果随着n的增长 时间或空间会以什么样的方式进行增长

例

for(int i = 0; i

二、时间复杂度怎么算

时间复杂度算法记作: T（n）=O（f（n））。

算法的时间复杂度，用来度量算法的运行时间，记作:T（n）=O（f（n））。它表示随着输入大小n的增大，算法执行需要的时间的增长速度可以用f（n）来描述。因为f（n）的增长速度是大于或者等于T（n）的，即T（n）=O（f（n））。

所以我们可以用f（n）的增长速度来度量T（n）的增长速度，所以我们说这个算法的时间复杂度是O(f(n))。如果一个算法的执行次数是T（n），那么只保留最高次项，同时忽略最高项的系数后得到函数f（n），此时算法的时间复杂度就是O（f（n））。

时间复杂度

在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。

使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。为了计算时间复杂度，我们通常会估计算法的操作单元数量，每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。

三、一文讲透算法中的时间复杂度和空间复杂度计算方式

作为一名“程序猿”，大家应该都听过这么一句话：程序=数据结构+算法。

这句话是由瑞士计算机科学家尼古拉斯·沃斯（Niklaus Wirth）在 1984 年获得图灵奖时说的一句话，这位大佬还以这句话为名出了一本书《Algorithms + Data Structures=Programs》，从此这句话就成为了大家耳熟能详的一句名言。

随着时间的推移，不管这句话是不是非常准确，但至少能说明数据结构与算法对程序来说是非常核心的基础，如果我们想要写出更多优秀优雅的代码，那么数据结构与算法是必须要掌握好的。

很多人可能觉得，我不会算法，代码一样写得很"溜"，算法这东西似乎用处不大。现在互联网的发达，我们想要什么几乎都可以在网上找到现成的，各种框架功能十分强大，似乎看起来确实不用算法也可以写出“好代码”。然而假如我们不懂算法，比如项目中用到了排序，我们如何评估代码的执行效率？再比如最常用的 ArrayList 和 LinkedList ，我们该如何选择，又比如说我们需要去集合中找某一个数，又该如何写出性能优秀的代码呢？

同样的代码，如何判断谁的代码是优秀的代码？可读性，可扩展性，健壮性可能都可以用来判定，然而这些东西我觉得并不能直接体现出你代码的优秀，因为对用户而言，访问你的代码响应速度快那就是优秀的代码，相反，动辄响应几秒甚至更长时间的接口，恐怕就算你可读性再好，再健壮也称不上是好代码。

所以说一段代码是否优秀，最直接的判断标准就是性能，而如果要写出高性能的代码，那么就必须要了解算法，而且抛开这个因素，但凡不想一辈子都写 CRUD 代码的，也需要去了解算法，我们使用的很多框架和中间件底层都有数据结构和算法的身影，学好算法对我们源码阅读时理解其设计思想也是大有裨益的。

要说功利性的目的，那就是面试，目前很多大厂的面试，算法基本必面，所以想进大厂的话，咱们也得好好学学算法。

提到算法，很多人的第一反应就是太难学了，学不会，或者说经常是看完就忘了，但是其实对于我们一个普通的开发者而言，因为并不需要我们去发明算法，我们需要的仅仅只是去灵活的运用算法，所以并不需要非常扎实的数据基础，当然基本的数学常识还是要有的。

如果说需要去发明设计一款算法，那就要去推导去证明算法的可行性，这种是需要具有非常扎实的数学基础的，一般人确实无法做到，然而我们普通程序员口中提到算法无非是二分查找法，哈希算法等，高级一点的就还有回溯，贪心，动态规划等等，这些所谓的算法都是已经有现成的公式了，我们要做的无非就是理解它，然后灵活的运用它。这就和我们以前学习数学公式一样，给你一个公式，然后你去做题，做题的过程其实就是去灵活地运用这个公式。

算法也是同理，都是有特定方法和特定思路的，我们也并不需要去推导证明这种方式为什么可行，所以学习算法没有其他诀窍，就是先理解思路，然后多练，等熟练了，自然就可以灵活运用了，也不会说学了立刻就忘了。学完就忘无非两个原因，一是没理解，二是没有练习巩固。

数据结构与算法经常是放在一起讲，这两者是没办法独立的，因为算法是为了达到某种目的的一种实现方式，而数据结构是一种载体，也就是说算法必须依赖数据结构这种载体，否则就是空谈。换句话说：数据结构是为算法服务的，而算法又需要作用在特定的数据结构之上。

一个算法到底好不好，我们如何去评价？前面我们提到了，你的代码好不好，最直观的就是看响应速度，算法也一样，同样实现一个目的（比如说排序），谁的算法速度快，我们就可以认为谁的算法更优，如果说两种算法实现的速度差不多，那么我们还可以去评价算法所占用的空间，谁占用的空间少，那么就可以认为谁的算法更优，这就是算法的基础：时间复杂度和空间复杂度。

学习算法之前，我们必须要学会如何分析时间复杂度和空间复杂度（也就是“快”和“省”），否则自己写出来的算法自己都不知道算法的效率。

接触过算法的都知道，算法的时间复杂度是用大写的“O”来表示的，比如： O(1) ， O(n) ， O(logn) ， O(nlogn) ， O(n²) 等等。

变量指的是变量，也就是一段代码的执行时间是随着变量的变化而变化的，而不变指的是常量，也就是不论我的变量如何改变，执行时间都不会改变。

接下来我们就实际的来分析下常用时间复杂度的例子来练习一下。

0(1) 复杂度算法也称之为常数阶算法。这里的 1 是用来代指常量，也就是说这个算法的效率是固定的，无论你的数据量如何变化，效率都一样，这种复杂度也是最优的一种算法。

上面的示例中不论有多少行代码，时间复杂度都是属于常数阶段。换言之：只要代码不存在 循环 ， 递归 等循环类调用，不论代码有多少行，其复杂度都是常数阶。

O(n) 复杂度算法也称之为线性阶段。比如下面这个示例我们应该怎么分析复杂度呢？

前面常量阶没分析是因为常量阶比较容易理解，接下来我们就以线性阶这个为例子来分析下具体是怎么得到的。

我们假设每一行代码的执行时间是 T ，那么上面这段代码的执行复杂度是多少呢？

答案很明显，那就是 T+n*T ，也就是 (n+1)T ，而在算法中有一个原则，那就是常量可以被忽略，所以就得到了 nT ，换成大 O 表示法就是 O(n) 。

这只是一个简略的计算过程，大家也不用较真说每行代码执行时间可能不一样之类的，也不要较真说 for 循环占用了一行，下面的大括号也占用了一行，如果要较真这个，那我建议可以去想一下 1=1 为什么等于 2 。

算法中的复杂度反应的只是一个趋势，这里 O(n) 反应的就是一个趋势，也就是说随着 n 的变化，算法的执行时间是会降低的。

知道了上面的线性阶，那么平方阶就很好理解了，双层循环就是平方阶，同理，三次循环就是立方阶， k 次循环就是 k 次方阶。

O(logn) 也称之为对数阶，对数阶也很常见，像二分查找，二叉树之类的问题中会见到比较多的对数阶复杂度，但是对数阶也是比较难理解的一种算法复杂度。

下面我们还是来看一个例子：

这段代码又该如何分析复杂度呢？这段代码最关键的就是要分析出 while 循环中到底循环了多少次，我们观察这个循环，发现 i 并不是逐一递增，而是不断地翻倍： 1->2->4->8->16->32->64 一直到等于 n 为什么才会结束，所以我们得到了这样的一个公式： 2^x=n 。

也就是说我们只要计算出 x 的值，就得到了循环次数，而根据高中的数学知识我们可以得到 x=log2n （ 2 在下面，是底数，试了几种方法都打不出来，放弃了），所以根据上面线性阶的分析方法，我们省略常量，就得到了示例中的算法复杂度为 O(log2n) 。

同样的分析方式，下面的例子，我们可以很快地分析出复杂度就为 O(log3n) ：

上面得到的 log3n 我们可以再做进一步的转换： log3n=log32 * log2n ，而 log32 （注意这几个地方的情况 3 是底数，在下面） 是一个常量，常量可以省略，所以也就得到了： O(log3n)=O(log2n) 。同样的道理，不论底数是多少，其实最终都可以转化成和 O(log2n) 相等，正因为如此，为了方便，我们算法中通常就会省略底数，直接写作 O(logn) 。

上面的数学公式大家如果忘了或者看不懂也没关系，只要记住不论对数的底数是多少，我们都算作 O(logn) ，而对于一个算法的复杂度是否是对数阶，还有一个简易的判断方法： 当循环中下标以指定倍数形式衰减，那么这就是一个对数阶 。

如果理解了上面的对数阶，那么这种线性对数阶就非常好理解了，只需要在对数阶的算法中再嵌一层循环就是线性对数阶：

分析了前面这些最常用的时间复杂度，其实我们可以得到以下规律：

除了上面常用的复杂度之外，另外还有指数阶，阶层阶，根号阶等，这些接触的相对会较少，我们就不特意做分析了，如果大家感兴趣的话，可以自己去了解下。

前面我们分析的都是只有一段代码比较复杂的情况下得到的复杂度结果，那么假如我一个算法中，有多段代码都比较复杂呢？这时候复杂度该如何分析？

我们先看下面这个例子：

这个例子中有三个循环，首先第一个，是一个常量，那么根据前面的结论，不论这个常量是多大，都属于常量级，所以第一个循环中的复杂度为 O(1) ，第二个和第三个循环我们前面也分析过，复杂度分别为 O(n) 和 O(n²) 。

也就是这一段代码中有三段代码产生了三种不同复杂度，而且这三个复杂度可以很明显得到的大小关系为： O(1)<o(n)<o(n²) span=""> </o(n)<o(n²)> ，像这种在同一个算法中有明确大小关系的，我们就可以直接取最大值作为这个算法的复杂度，所以这个例子中算法的复杂度就是 O(n²) 。

接下来我们再来看一个例子：

这个例子我们同样对三段循环分别分析可以分别得到如下复杂度： O(1) ， O(m) ， O(n) 。这时候我们只能知道 O(1) 最小可以忽略，但是后面两个无法却无法确定大小，所以这时候我们需要取两段循环复杂度之和来作为算法的复杂度，所以可以得到这个例子的算法复杂度为： O(m+n) 。

上面分析的时间复杂度都是比较简单的，实际算法中可能会比示例中复杂的多，而且我们示例中只要是循环都是无脑循环，也就是一定从头循环到尾，然而实际中我们有时候并不需要从头循环到尾，可能中途就会结束循环，所以我们根据实际情况，又可以将时间复杂度从以下四个方面来进一步分析：

这四种类型的时间复杂度在这里只会介绍前面三种，因为第四种比较复杂，而且使用场景也非常有限，而且对于这四种复杂度的分析，大家也作为了解就可以，不敢兴趣的朋友们可以跳过这一小部分，因为在绝大部分情况我们只需要分析最坏复杂度就行，也就是假设循环全部执行完毕场景下的时间复杂度。

我们通过一个例子来理解下最好时间复杂度：

这个方法就是在一个指定数组中找到指定元素的下标，找不到就返回 -1 ，这个方法比较简单，应该比较好理解。

注意这个方法中的循环体，如果找到元素，那么就直接返回，这就会有一个现象，那就是我这个循环体到底会循环多少次是不确定的，可能是 1 次，也可能是 n （假设数组的长度） 次，所以假如我们要找的元素就在数组中的第一个位置，那么我循环一次就找到了，这个算法的复杂度就是 O(1) ，这就是最好情况时间复杂度。

理解了最好时间复杂度，那么最坏时间复杂度也很好理解了，那就是数组中不存在我要找到元素，或者说最后一个值才是我要找的元素，那么这样我就必须循环完整个数组，那么时间复杂度就是 O(n) ，这也就是最坏时间复杂度。

最好时间复杂度和最坏时间复杂度毕竟只有特殊情况才会发生，概率还是相对较小，所以我们很容易就想到我们也需要有一个平均时间复杂度。

我们简单的来分析一下，为了便于分析，我们假设一个元素在数组和不在数组中的概率都为 1/2 ，然后假如在数组在，那么又假设元素出现在每个位置的概率也是一样的，也就是每个位置出现元素的概率为： 1/n 。

所以最终得到的平均时间复杂度应该等于元素在数组中和元素不在数组中两种情况相加。

因为元素在数组中的概率为 1/2 ，然后在每个位置出现的概率也为 1/n 。假如元素出现在第一个位置，复杂度为 1*(1/2n) ；假如元素出现在第二个位置，复杂度为 2 * (1/2n) ，最终得到当前场景下时间复杂度为： 1*(1/2n) + 2 * (1/2n) + ... + n*(1/2n) =(n+1)/4。

前面已经假定了元素不在数组中的概率为 1/2 ，所以当前场景下的时间复杂度为： n * (1/2) ，因为元素不在数组中，那么这个算法必然会将整个循环执行完毕，也就循环是 n 次。

最后我们把两种情况的复杂度之和相加就得到了平均时间复杂度： (n+1)/4 + n/2 = (3n+1)/4 ，最终我们将常数类的系数忽略掉，就得到了平均时间复杂度为 O(n) 。

均摊时间复杂度的算法需要使用摊还分析法，计算方式相对有点复杂，而且使用场景很有限，本文就不做过多介绍了。

空间复杂度全称就是渐进空间复杂度，用来表示算法的存储空间与数据规模之间的增长关系。和时间复杂度一样，空间复杂度也是用大 O 进行表示。

其实学会了分析时间复杂度，那么空间复杂度的分析就简单了，主要就看我们在一个算法当中到底有没有使用到了额外的空间来进行存储数据，然后判断这个额外空间的大小会不会随着 n 的变化而变化，从而得到空间复杂度。

我们来看一个给数组赋值例子，假设这就是一个算法，我们可以来分析下这个算法的空间复杂度：

一开始定义了一个变量，这里需要空间，但是这是一个常量级的（不随 n 的变化而变化），然后再定义了一个数组，数组的长度为 n ，这里数组也需要占用空间，而且数组的空间是随着 n 的变化而变化的，其余代码没有占用额外空间，所以我们就可以认为上面示例中的空间复杂度为 O(n) 。

对于算法的空间复杂度也可以简单的进行总结一下：

本文主要讲述了为什么要学习算法，也简单减少了数据结构与算法之间的关系，随后主要介绍了算法中的入门知识：时间复杂度和空间复杂度。想要学好算法，必须要掌握如何分析一个算法的时间复杂度和空间复杂度，只有自己会分析这两个个衡量算法主要性能的标准，才能更好的写出性能优秀的算法，同时我们也讲到了最好时间复杂度，最坏时间复杂度，平均时间复杂度和均摊时间复杂度，不过这四种复杂度的计算方式大家作为了解即可，等实际确实需要使用到再来回顾也不迟。

四、究竟什么是时间复杂度，怎么求时间复杂度，看这一篇就够了

时间复杂度就是用来方便开发者估算出程序的运行时间

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

假设算法的问题规模为n，那么操作单元数量便用函数f(n)来表示

随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为 O(f(n))

这里就要说一下这个大O，什么是大O呢，很多同学说时间复杂度的时候都知道O(n)，O(n^2)，但说不清什么是大O

算法导论给出的解释： 大O用来表示上界的 ，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

同样算法导论给出了例子：拿插入排序来说，插入排序的时间复杂度我们都说是O(n^2)

但是在数据本来有序的情况下时间复杂度是O(n)，也就对于所有输入情况来说，最坏是O(n^2) 的时间复杂度，所以称插入排序的时间复杂度为O(n^2)

同样的同理我们在看一下快速排序，都知道快速排序是O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2) 的，严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^2)

但是我们依然说快速排序是O(nlogn)的时间复杂度，这个就是业内的一个默认规定，我们这里说的O 代表的就是一般情况，不是严格的上界

所以这里大家知道这么一回事就好了

面试中面试官绝对不会针对快速排序的时间复杂度问题来讨论O的定义， 大家知道讨论的时间复杂度就是指一般情况下的时间复杂度就好了。

大家要对算法的时间复杂度有这样的一个概念

就是同一个算法的时间复杂度不是一成不变的，和输入的数据形式依然有关系

我们主要关心的还是一般情况下的数据形式 。

面试中说道算法的时间复杂度是多少指的都是一般情况

但是如果面试官和我们深入探讨一个算法的实现以及性能的时候 我们就要时刻想着 数据用例的不一样 时间复杂度也是不同的，这一点同学们要注意

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

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

就像上图中图中 O(5n^2) 和 O(100n) 在n为20之前 很明显 O(5n^2)是更优的，所花费的时间也是最少的。

那我们为什么在计算时间复杂度的时候要忽略常数项系数呢，也就说O(100n) 就是O(n)的时间复杂度，O(5n^2) 就是O(n^2)的时间复杂度

而且要默认O(n) 优于O(n^2) 呢 ？

这里就又涉及到大O的定义

因为 大O其实就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度 ，这个点也就是 常数项系数已经不起决定性作用的点。

例如上图中 20 就是那个点 ，n只要大于20 常数项系数已经不起决定性作用了。

所以我们说的时间复杂度都是省略常数项系数的，是因为一般情况下我们都是默认数据规模足够的大，基于这样的事实 我们给出的算法时间复杂的的一个排行如下所示：

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)(立方阶) < O(2^n) (指数阶)

我们平时说这个 算法的时间复杂度是logn的，一定是log 以2为底n的对数么？

其实不然，也可以是以10为底n的对数，也可以是以20为底n的对数，但我们统一说 logn，也就是忽略底数的描述。

为什么可以这么做呢？

如下图所示

假如我们有两个算法的时间复杂度 分别是log以2为底n的对数 和 log 以10为底n的对数

那么这里如果大家还记得我们高中数学的话， 应该不能理解 以2为底n的对数 = 以2为底10的对数 乘以 以10为底n的对数

那这里以2为底10的对数 是一个常数，而我在上面已经讲述了我们计算时间复杂度是忽略常数项系数的

抽象一下 log 以i为底n的对数 等于 log 以j为底n的对数，所以我们忽略了i，直接说是logn，正式因为logij 是就一个常数

所以，这样就应该不难理解了 我们为什么忽略底数了

有时候，我们去计算时间复杂度的时候 发现不是一个 简单的O(n) 或者O(n^2)， 而是一个复杂的表达式，例如：

O(2*n^2 + 10*n + 1000)

那这里我们通常如何描述这个算法的时间复杂度呢，一种方法就是简化法

去掉运行时间中的加法常数项 （因为常数项并不会因为n的增大而增加计算机的操作次数）

O(2*n^2 + 10*n)

去掉常数系数 （我们刚刚已经详细讲过为什么可以去掉常数项的原因了）

O(n^2 + n)

只保留保留最高项 去掉数量级小一级的n （因为n^2 的数据规模远大于 n），最终简化为：

O(n^2)

如果这一步同学们理解有困难，那也可以做提取n的操作，变成 O(n(n+1)) ，省略加法常数项后 也别变成了

O(n^2)

所以最后我们说：我们这个算法的算法时间复杂度是 O(n^2)

也可以用另一种简化的思路，当n大于40的时候 ， 这个复杂度 会一直小于 O(3*n^2)

O(2*n^2 + 10*n + 1000) < O(3*n^2)

所以说 最后我们省略掉常数项系数最终时间复杂度也是 O(n^2)

我们通过一道题目，来看一下具体时间复杂度应该怎么算

题目描述：找出n个字符串中相同的两个字符串（假设这里只有两个相同的字符串）

一些同学可能以为解决这道题目可以采用枚举遍历的解法，时间复杂度是 O(n^2)

这个时间复杂度其实是不对的。

这里 一些同学忽略了字符串比较的时间消耗，这里并不像int 型数字做比较那么简单

除了n^2 次的遍历次数外， 字符串比较依然要消耗m次操作（m也就是字母串的长度），所以时间复杂度是 O(m*n*n)

那么我们再想一下其他解题思路

我们先排对n个字符串按字典序来排序，排序后n个字符串就是有序的，意味着两个相同的字符串就是挨在一起

然后在遍历一遍n个字符串，这样就找到两个相同的字符串了

那我们来看看这种算法的时间复杂度

快速排序时间复杂度 为O(nlogn)，依然要考虑字符串的长度是m，那么快速排序每次的比较都要有m次的字符比较的操作，就是 O(m*n*logn)

之后我们还要遍历一遍这n个字符串找出两个相同的字符串，别忘了遍历的时候依然要比较字符串，所以总共的时间复杂度是 O(m*n*logn + n*m)

我们对 O(m*n*logn + n*m) 进行简化操作，把 m*n 提取出来变成 O(m*n*(logn + 1)) ，

在省略常数项最后的时间复杂度是 O(m*n*logn) ， 那我们比较一下时间效率 O(m*n*logn) 是不是比第一种方法 O(m*n*n) 更快一些呢

很明显 O(m*n*logn) 要优于 O(m*n*n)

所以 先把字符串集合排序在遍历一遍找到两个相同字符串的方式要比直接暴力枚举的方式更快 。

通过这个例子 希望大家对时间复杂的是怎么算的有一个初步的理解和认识。

以上就是关于计算复杂度和时间复杂度相关问题的回答。希望能帮到你，如有更多相关问题，您也可以联系我们的客服进行咨询，客服也会为您讲解更多精彩的知识和内容。

推荐阅读：

杭州计算机工资怎么样（杭州计算机工资怎么样知乎）

给水水力计算图（给水工程水力计算表）

指数在计算器上怎么按

英文版狗屁文章生成器

东莞长安百立英语招聘（东莞长安百力厂好不好）