时间复杂度与空间复杂度简单理解

男娘i 2021-09-30 04:12 289阅读 0赞

首先，时间复杂度与空间复杂度是对立的，时间复杂度越低，空间复杂度就越高。我们在程序中通常采用以空间换时间的方式来提高项目运行效率。

**一、时间复杂度**

先给大家说一个最常见的简单的，时间复杂度是以n为变量，程序的运行次数随n的变化而变化。

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

当只有一层for循环的时候时间复杂度就是O（n）如果两层for循环如下所示：

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

那么它时间间复杂度就是O（n^2）,同理三层for循环就是O（n^3）

2. 常数时间复杂度

int i=0;
    i=(i+n)*n;
    system.out.println("我只执行一次"+i);

当我们的语句是一句一句向下执行时，执行多少语句，时间复杂度都是O(1)

3.**对数阶**  
接着看如下代码：

int number=1;
    
    while(number<n){
       
    
    number=number*2;
    
    //时间复杂度为O(1)的算法
    
    …
    
    }

*  可以看出上面的代码，随着number每次乘以2后，都会越来越接近n，当number不小于n时就会退出循环。假设循环的次数为X，则由2^x=n得出x=log₂n，因此得出这个算法的时间复杂度为O(logn)。

**二、空间复杂度**

一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。　　  
（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。  
（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。  
一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))　　其中n为问题的规模，S(n)表示空间复杂度。

【考考你】

好了，我想到这里，两个复杂度的意思你是否已经弄明白了吧，明白的点个赞，没明白的留个言。

明白的，不妨试试看看那下面这段代码的时间复杂度T(n)、空间复杂度S(n)分别是多少？回答后连续下滑查看答案。

for(int i=0; i<n; i++) {
        int[] arr1 = new int [5];
        for (int j = 0; j < n/2; j++) {
            int[] arr2 = new int [n];
        }
    }

解：

从这里看出：T(n) = (1/2) n^2，S(n) = (1/2) n^3 + 5n

随着n趋于无穷大的时候，最影响他们的是(1/2) n^2和(1/2) n^3，我们省略其常数系数即可得到复杂度关系，即这段代码的时间复杂度为T(n) = O( n^2)，空间复杂度为S(n) = O(n^3)

注：空间复杂度即占用空间大小，这里变量占用空间为5n+(1/2) n^3,即变量个数。