什么是算法的时间复杂度和空间复杂度?,算法的时间复杂度和空间复杂度有关吗
本文将学习算法，介绍算法的时间复杂度和空间复杂度，希望对大家有所帮助！
算法是指一套用于操纵数据和解决程序问题的方法。对于同一个问题，如果使用不同的算法，最终的结果可能是一样的，但是过程中消耗的资源和时间会有很大的不同。
那么应该如何衡量不同算法的优劣呢？
主要从算法占用的“时间”和“空间”两个维度来考虑。
时间维度：指执行当前算法所用的时间。我们通常用“时间复杂度”来描述。
空间维度：指执行当前算法需要多少内存空间。我们通常用“空间复杂度”来描述。
因此，评价一个算法的效率主要看它的时间复杂度和空间复杂度。但是，有时候时间和空间是“鱼和熊掌”，我们需要在两者之间取得平衡。
我来分别介绍一下时间复杂度和空间复杂度的计算方法。
一、时间复杂度
我们想知道一个算法的“时间复杂度”。很多人想到的第一个方法就是运行一次这个算法程序，那么所用的时间自然就知道了。
这样可以吗？当然，但是它也有许多缺点。
这种方法很容易受到运行环境的影响，在高性能机器上运行的结果会和在低性能机器上运行的结果有很大的不同。而且与测试中使用的数据规模也有很大关系。此外，当我们编写算法时，没有办法完全运行它。
于是，另一种更一般的方法出来了：“ 大O符号表示法”，即T(n)=O(f(n))
我们先来看一个例子：
for(I=1；I=n；我)
{
j=I；
j；
}通过“大O符号表示法 ”，这个码的时间复杂度为：O(n)。为什么？
在大O记法中，时间复杂度的公式为：T(n)=O( f(n))，其中f(n)表示每行代码执行次数之和，O表示比例关系。这个公式的全称是：算法的渐进时间复杂度。
我们继续看上面的例子，假设每行代码的执行时间是一样的，我们用1粒子时间来表示。那么这个例子的第一行用了1个粒子时间，第三行用了n个粒子时间，第四行用了n个粒子时间(第二行和第五行是符号，暂时忽略)，那么总时间就是1个粒子时间n个粒子时间n个粒子时间，也就是(1 2n)个粒子时间，也就是T(n)=(1 2n)*个粒子时间。从这个结果可以看出，这个算法的时间消耗是随着n的变化而变化的，因此，我们可以简单地把这个算法的时间复杂度表示为：T(n)=O(n)
为什么可以简化成这样？因为大O符号不是用来真实表示算法的执行时间，而是用来表示代码执行时间的增长趋势。
所以在上面的例子中，如果n是无穷大，T(n)=time(1 2n)中的常数1是没有意义的，倍数2也是没有意义的。所以可以简单简化为T(n)=O(n)。
常见的时间复杂度顺序是：
常数阶O(1)
登录订单O(登录)
O(n)的线性阶
线性对数阶O(nlogN)
订单o (n)
三次o (n)
k阶o (n k)
指数级(2 n)
从上到下的时间复杂度越来越大，执行的效率越来越低。
下面是一些常见的来解释一下(顺序不严格):
常数阶O(1)
不管代码执行多少行，只要没有循环等复杂结构，这段代码的时间复杂度都是O(1)，比如：
int I=1；
int j=2；
我；
j；
int m=I j；上面的代码在执行时，它的消耗时间并不随着某个变量的增长而增加，所以这类代码无论有多长，即使有上万行，它的时间复杂度也可以用O(1)来表示。
线性阶O(n)
这在第一个代码示例中进行了解释，例如：
for(I=1；I=n；我)
{
j=I；
j；
}这段代码，for循环中的代码会执行n次，所以它消耗的时间是随着n的变化而变化的，因此，这类代码可以用O(n)来表示它的时间复杂度。
对数阶O(logN)
还是先看代码：
int I=1；
当(在)
{
I=I * 2；
}从上面的代码可以看出，在while循环中，I每次都要乘以2。乘法之后，I越来越接近n，我们来试着解一下。假设循环重复x次后，I大于2，然后循环退出。也就是说，2的x次方等于n，那么x=log2 n。
也就是说，登录2 n次后，代码结束。因此，这段代码的时间复杂度为：O(logn)
线性对数阶O(nlogN)
线性对数阶O(nlogN)其实很好理解。如果时间复杂度为O(logn)的码循环n次，那么它的时间复杂度为n * O(logN)，也就是O(nlogN)。
以上面稍加修改的代码为例：
for(m=1；Mn；m)
{
I=1；
当(在)
{
I=I * 2；
}
}平方阶O(n)
O(n)的平方阶更容易理解。如果再次嵌套O (n)的代码，其时间复杂度将为O (n)。
示例：
for(x=1；I=n；x)
{
for(I=1；I=n；我)
{
j=I；
j；
}
}这段代码实际上嵌套了2层N个循环，其时间复杂度为O(n*n)，即O(n)
如果一层循环的N变为M，即：
for(x=1；I=m；x)
{
for(I=1；I=n；我)
{
j=I；
j；
}
}那么它的时间复杂度就变成O(m*n)
立方阶O(n)、K次方阶O(n^k)
参考上面的O (n)就明白了。O (n)相当于三层N循环，其他也差不多。
除此之外，其实还有平均时间复杂度、平均时间复杂度、最差时间复杂度、最佳时间复杂度的分析方法，有点复杂，这里就不展开了。
二、空间复杂度
既然时间复杂度不是用来计算程序的具体时间消耗的，那么我也应该明白空间复杂度不是用来计算程序实际占用的空间的。
空间复杂度是一个算法在运行过程中暂时占用的存储空间的度量，也反映了一种趋势，用S(n)来定义。
空间复杂度常用的有：O(1)，O (n)，O(n)。让我们来看看：
空间复杂度 O(1)
如果算法执行所需的临时空间不随变量N的大小而变化，即该算法的空间复杂度为常数，可表示为O(1)
示例：
int I=1；
int j=2；
我；
j；
int m=I j；码中I、J、M分配的空间不随处理的数据量而变化，所以其空间复杂度S(n)=O(1)
空间复杂度 O(n)
我们先来看一个代码：
int[] m=new int[n]
for(I=1；I=n；我)
{
j=I；
j；
}这段代码中，新数组的第一行出来，这个数据的大小是n，这段代码的2-6行虽然有循环，但是没有分配新的空间。所以这个码的空间复杂度主要取决于第一行，即S(n)=O(n)
以上是对算法的时间复杂度和空间复杂度的分析。欢迎与我们交流。
有关算法的更多信息，请访问：编程入门！上面的文章是关于算法的时间复杂度和空间复杂度的细节。请多关注我们的其他相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。