为什么线性搜索的空间复杂度是O(1)而非O(n)？

结论 #

大家常说的线性搜索空间复杂度为O(1)，指代的是额外空间复杂度（辅助空间），这是算法领域讨论空间复杂度的默认口径，你提到的包含输入存储空间的计算口径极少在算法复杂度讨论场景使用。

两种空间复杂度口径的差异 #

你查到的定义是广义的总空间复杂度：包含输入本身占用的空间 + 算法运行额外需要的辅助空间。如果按这个口径计算，线性搜索总空间确实是O(n)，但这个口径没有实际参考价值——输入是算法处理的前置条件，不存在“优化掉输入空间”的可能，所有处理n个输入元素的算法总空间复杂度最少都是O(n)，无法体现不同算法的空间开销差异。
行业默认讨论的“空间复杂度”默认指额外空间复杂度：仅计算算法运行过程中，除了输入数据本身占用的空间之外，额外需要申请的内存空间大小，这个指标才能体现算法本身的空间消耗水平。
只有在评估完整程序的总内存占用这类工程场景下，才会计算包含输入空间的总内存开销，这种场景下不会用“算法空间复杂度”这个术语来表述。

对应示例代码的验证 #

你给出的线性搜索C++实现如下：

#include<iostream>

int linearSearch(int array[], int length, int value){
    int location = -1;
    for(int i = 0; i < length; i++){
        if(array[i] == value){
            location = i;
            break;
        }
    }
    
    return location;
}

int main(){
    
    int value = 40;
    
    int data[] = {0,1,2,3,4,-5,6,7,8,9,-10};
    int length = sizeof(data)/sizeof(int);
    
    int location = linearSearch(data, length, value);
    
    if(location == -1){
        std::cout << "Element not found!\n";
    }
    else{
        std::cout << "Element present at : " << location << std::endl;
    }
}

可以看到linearSearch函数传入的array是指针，不会额外复制整个输入数组，函数内部仅定义了location、i两个固定大小的局部变量，不管输入数组的长度n有多大，这部分额外开销都是固定的，因此额外空间复杂度为O(1)，也就是大家常说的线性搜索空间复杂度O(1)。

内容的提问来源于stack exchange，提问作者S. Tiss