怎么确定算法的空间复杂度

Question

怎么确定算法的空间复杂度

#include<stdio.h>
#include<String.h>
int lengthOfLongestSubstring(char * s){
    if (s == NULL) return 0;
    int max = 0;          //记录最长的长度max
    int left = 0, right = 0;  //滑动窗口的左边界和右边界
    int dict[256] = {0};      //和前面的排序一样，搞个类似于哈希表的东西，通过数组记录其出现的相应次数；
    int index;
    for (; s[right] != '\0' ; right++){
        index = s[right];                            //得到对应字符的下标
        if(dict[index] > left) 
        left = dict[index];
        dict[index] = right+1;                            //注意：到只有一个字符时长度为1，所以这里右边界要加1
        if (max < right-left+1) 
        max = right-left+1; //更新最大值
    }
    return max;
}
main(){
 char a[99];
 gets(a);
 int n;
 n = lengthOfLongestSubstring(a);
 printf("%d",n);
}

Answer 1

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

（1）O(1)单个变量所占的空间永远为1

（2）O(n)数组里面有n个值，占用了n个内存单元

（3）O(n^2)可以想象为一个正方形，边长为n，存储了n的二次方个变量