【算法笔记】时间复杂度(Time complexity) 和 空间复杂度(Space Complexity)

我们讨论一些算法的时候，会经常听说时间复杂度和空间复杂度。

之前的工作中一般不会用到算法，加上我又不是计算机专业，对这些不太熟悉。
趁这几天有时间，简单的整理了一下时间复杂度和空间复杂度是什么。

1.时间复杂度

首先时间复杂度是用大O表示的。
我们看看维基百科是如何整理的。

图片备用地址

看这些眼花缭乱，初学者别看了…^^;;
其实结合代码看的话，一些常用的时间复杂度还是很好理解的。

常数阶O(1)

int i = 1;
int j = 2;
int n = i + j;
... ...

像这种无论代码执行了多少行，只要是没有循环等复杂结构，时间复杂度都是O(1)来表示。
为什么？ 因为再怎么复杂也是，只是执行了一遍而已。

线性阶O(n)

int j = 1
for(i=1; i<=n; ++i)
{
   j++;
}

for循环里执行n遍，消耗的时间是随着n的变化而变化的，
这类代码都可以用O(n)来表示它的时间复杂度。

这里补充说明一下，举例子: f(n) = 3n + 7。  
时间复杂度是O(f(n)), 这里可以看出时间的复杂度是随着n的变化而变化。  
所以时时间复杂度直接表示为 O(n), 也就是说O(f(n)) 直接简化成 O(n)。  

对数阶O(logN)

int i = 1;
while(i<m)
{
    i = i * 2;
}

这里的循环是，2的n次方小于m的时候结束。
所以这个时间复杂度是O(log2^n)。按照上述表示法，可以用O(logN)来表示了。

线性对数阶O(nlogN)

如果理解上述的表示方式，这个就很好理解了。O(n)里有O(logN)的复杂度了。
可以参考下面的代码。

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

平方阶O(n²)

这也一样了，O(n)里在嵌O(n)了。

int k = 1
for(j=1; j<=n; j++)
{
    for(i=1; i<=n; i++)
    {
        k++;
    }
}

立方阶O(n³)

那这就是O(n)里在嵌O(n)里面还有O(n)了。

int x = 1
for(k=1; k<=n; k++)
{
    for(j=1; j<=n; j++)
    {
        for(i=1; i<=n; i++)
        {
            x++;
        }
    }
}

剩余的可以自行了解…^^ 下面我们看看空间复杂度。

2.空间复杂度

空间复杂度通常也使用大O表示。
我们先看看维基百科是如何整理的。

空间复杂度是相应计算问题的输入值的长度的函数，它表示一个算法完全执行所需要的存储空间大小。
和时间复杂度类似，空间复杂度通常也使用大O记号来渐进地表示，例如O(n), O(nlogn), O(n^a), O(2^n)等；
其中n用来表示输入的长度，该值可以影响算法的空间复杂度。
就像时间复杂度的计算不考虑算法所使用的空间大小一样，空间复杂度也不考虑算法运行需要的时间长短。

我们就简单的看看空间复杂度为O(n)的代码

var m = new int[n]
for(i=1; i<=n; ++i)
{
   j++;
}

虽然这里做了一些循环，但是我们表示空间复杂度的时候，只考虑我们占有的空间，
所以第一行里分配了n的空间，空间复杂度为O(n)。
如果声明的是 int[n][n]的话空间复杂度就是O(n²)了。

以上是我对时间复杂度和空间复杂度的整理。
实际运用的时候，根据运行环境合理的分配时间和空间。

欢迎大家的意见和交流

email: li_mingxie@163.com