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

数据结构时间复杂度和空间复杂度如何计算

时间复杂度和空间复杂度

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

其实就是所耗时间与空间关于输入数据规模的函数

一般输入数据规模越大，所耗时间和空间就越多

如果所耗时间与数据规模成正比

时间复杂度就是 O(n）

如果所耗时间与数据规模的平方成正比

时间复杂度就是 O(n^2）

同理有O(n^3）O(n^4） O(nlogn） O(2^n）等复杂度

空间复杂度跟时间复杂度的意思是一样的

算法的复杂度和时间复杂度的关系？

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变，即可能导致占用较多的存储空间；反之，求一个较好的空间复杂度时，可能会使时间复杂度的性能变，即可能导致占用较长的运行时间。

另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。

什么是算法,解释算法的时间复杂度和空间复杂度

解决问题步骤的有限是算法，算法的时间复杂度和空间复杂度内容如下：

（1）时间复杂度是与求解问题规模、算法输入相关的函数,该函数表示算法运行所花费的时间。记为,T(n),其中,n代表求解问题的规模。算法的空间复杂度(Space complexity)度量算法的空间复杂性、即执行算法的程序在计算机中运行所占用空间的大小。

时间复杂度是一个函数，它定性描述了该算法的运行时间。同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

（2）简单讲,空间复杂度也是与求解问题规模、算法输入相关的函数。记为,S(n),其中,n代表求解问题的规模。 时间复杂度和空间复杂度同样,引入符号“O”来表示T(n)、S(n)与求解问题规模n之间的数量级关系。

算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

时间复杂度及其计算

算法是指解题方而完整的描述，是一系列解决问题的清晰指令，算法代表着 用系统的方法描述解决问题的策略机制 。对于同一个问题的解决，可能会存在着不同的算法，为了衡量一个算法的优劣，提出了空间复杂度与时间复杂度这两个概念。

一个算法是由 控制结构（顺序、分支和循环3种） 和 原操作（指固有数据类型的操作） 构成的，则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法，通常的做法是：

从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。

参考文章： 算法的时间复杂度和空间复杂度-总结

时间复杂度，又称时间频度，即 一个算法执行所耗费的时间 。

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

n称为 问题的规模 ，当n不断变化时，时间频度T(n)也会不断变化。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示， 若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。简单来说，就是T(n)在n趋于正无穷时也就跟f(n)不多大。

算法中语句执行次数为一个常数，则时间复杂度为O(1)。常见的时间复杂度有：

常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(n log2n),平方阶O(n2)，立方阶O(n3),...。

Log28：2为底N的对数，即2的几次方等于8，值为3

常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(n log2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

即：常数阶 < 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 立方阶 < … < 指数阶 < 阶乘

如：

第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n1+n2+n3)=Ο(n3)。

Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法。

指数函数：y=ax，对数函数：y=logax，幂函数：y=xa

x为变量，a为常量

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

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

我们该如何估计程序运行时间呢，我们通常会估计算法的操作单元数量，来代表程序消耗的时间， 这里我们默认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(2n^2 + 10n + 1000)

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

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

O(2n^2 + 10n)

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

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(3n^2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我们对 O(mnlogn + nm) 进行简化操作，把 mn 提取出来变成 O(mn(logn + 1)) ，

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

很明显 O(mnlogn) 要优于 O(mnn)

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

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