【数据结构与算法】十 █算法复杂度█ 二空间复杂度

以你之姓@ 2022-08-21 04:20 198阅读 0赞

# **【数据结构与算法】十 █算法复杂度█ 二 空间复杂度**  #

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

分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说，一般都比较简短，算法本身所占用的存储空间较少，但运行时需要一个附加堆栈，从而占用较多的临时工作单元；若写成非递归算法，一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。

--------------------

我们以上一章节中介绍的算法为例进行说明

# **例 一** #

#include <iostream>
    using namespace std;
    
    template <class T>
    int getArrayLen(T& array){
        return sizeof(array) / sizeof(array[0]) ;
    }
    
    
    template <class T>
    int binary_search (T& array , int key , int begin , int end){
        if(begin >= end)
            return -1;
        int middle = (begin+end) / 2;
        if(array[middle] > key)
            return binary_search(array , key , begin , middle);
        else if(array[middle] < key)
            return binary_search(array , key , middle + 1 , end);
        else
            return middle;
    }
    
    
    int main(){
        int i=-2 , array[] = {
       0,1,2,3,6,7,8,9};
        for(;i<15;i++)
            cout << "searching : " << i <<  "\t\t position : " << binary_search(array , i , 0 , getArrayLen(array)) << endl;
        return 0;
    }

--------------------

# **静态空间** #

我们的binary\_search方法中传入引用array,三个int类型的变量(key,begin,end),在方法中定义了一个middle变量.那么这些变量(除引用类型 array外,引用传值特性)都需要在binary\_search中有相应的存储空间,这些变量所用的空间和binary\_search方法代码块在运行是所占用的内存空间我们称为静态空间.

--------------------

# **可变空间** #

#### **递归栈所需的空间** ####

我们看到例 一中用的额是递归的方法来实现二分查找.那么就会出现递归栈所需要的空间,我们来用一个图形说明.

![这里写图片描述][20160319163719440]  
调用关系 当只有n-1的binary\_search 返回后  
n-2的binary\_search才会返回,依次类推 …  
深度longN … 那么空间复杂度是logN

--------------------

# **例 二** #

#include <iostream>
    using namespace std;
    
    template <class T>
    int getArrayLen(T& array){
        return sizeof(array) / sizeof(array[0]) ;
    }
    
    
    template <class T>
    int binary_search_iterative(T& array, int key, int begin, int end){
        int middle ;
        while(begin < end){
            middle = (begin+end) / 2;
            if(array[middle] > key)
                end = middle;
            else if(array[middle] < key)
                begin = middle + 1;
            else
                return middle;
        }
        return -1;
    }
    
    
    
    
    int main(){
        int i=-2 , array[] = {
       0,1,2,3,6,7,8,9};
        for(;i<15;i++)
            cout << "searching : " << i <<  "\t\t position : " << binary_search_iterative(array , i , 0 , getArrayLen(array)) << endl;
        return 0;
    }

例二的二分查找是由迭代来完成的,那么它就不会存在**递归栈所需的空间**.所以例二的空间复杂度是O(1)

--------------------

# **最后** #

通过上面一些简单的讲解，  
相信朋友们已经知道其原理及特性了。  
本人能力有限,  
如发现错误或不合理欢迎指正…

--------------------

[20160319163719440]: /images/20220731/8ab299edb5e048119170a21b0124f654.png