计算机常识细节整理（一）时间复杂度和空间复杂度

一. 什么是算法：是指用来操作数据，解决程序问题的一组方法。对于同一个问题，使用不同的算法，结果是一样的，但是过程中所消耗的资源和时间却会有很大的区别。

二. 从哪些角度衡量消耗资源的多少：时间维度，空间维度。

时间维度：指当前算法所消耗的时间——>时间复杂度

空间维度：指当前算法需要占用的内存空间——>空间复杂度

# 使用什么样的算法来实现，需要在时间，空间复杂度之间进行取舍，权衡。

三. 时间复杂度

公式：T(n) = O(f(n)) ——>大O表示法

通过举例说明：

解释：图片中第一行的执行次数，只有一次；

           第三行的执行次数，有n次；

           第四行的执行次数，有n次；

           综合以上，计算出来的总的执行次数为：f(n)=1+n+n=2n+1;

           如果当n为无穷大的时候，1可忽略不计，即f(n)=2n，此时f(n)随着n的数值变化而变化，而

           时间复杂度T(n)=O(f(n))，即可简化表达为T(n)=O(n)。

四. 常见的时间复杂度量级有：

• 常数阶O(1)
• 对数阶O(logN)
• 线性阶O(n)
• 线性对数阶O(nlogN)
• 平方阶O(n²)
• 立方阶O(n³)
• K次方阶O(n^k)
• 指数阶(2^n)

 常数阶O(1)：无论执行多少次，没有循环就是常数阶。

 线性阶O(n)：上面例子。

 对数阶O(logN)：

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

该例子中，i从初始值开始，每次乘以2，不断的接近n，假设x次乘以2之后，i的值大于等于了n，那么是否可以得出，2的n次方等于x，那么x = log2^n，则简化后，时间复杂度为O(logn)。

线性对数阶O(nlogN)：举例如下

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

 复杂度为对数阶的程序，执行n次，时间复杂度即为线性对数阶。

平方阶O(n²)：线性阶复杂度的程序，循环执行n次。

立方阶O(n³)：线性阶三层嵌套。

五. 常用的空间复杂度：

O(1)——>如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量。

O(n)——>

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

O(n*n)——>以此类推