算法的空间复杂度

1. 输入数据所占的空间
2. 算法程序本身所占的空间
3. 辅助变量所占的空间

拓展：

算法本身所占空间虽然和算法有关，但一般大小是相对固定的。所以在研究算法的空间复杂度时，只需分析除数据和算法本身之外的辅助空间即可。算法的空间复杂度一般指的是算法执行过程中所占的辅助空间大小，用S（n）表示，与时间复杂度一样，也可以用S（n）=O（n）表示，当然这里的n也是随着问题的规模增大，算法运行所在需存储量的增长率与g（n）的增长率相同（空间复杂度相对于时间复杂度，没那么重要）

牛刀小试

非递归算法分析

仅仅依赖于问题规模的时间复杂度，这类问题的操作都具有普遍性，也就是说对所有的数据均等价地处理。（这里问题较为容易）

Case1：

Temp =i;
i=j;
j=temp;
复制代码

分析：

以上三条单个语句的频度都是为1，该算法段的执行时间是一个与问题规模n无关的常数，所以算法的时间复杂度为常数阶 ，即T（n）=O（1）；注意：只要不随问题规模n的增加而增长，即使算法中有上千条语句，时间复杂度仍然是一个比较大的常数而已。因此此类算法的时间复杂度为O（1）

Case2：

x=0;y=0;
for(k-1;k<=n;k++){
    x++;
    for(i=1;i<=n;i++){
      for(j=1;j<=n;j++){
            y++;
        }
    }
}
复制代码

分析：

当有若干个循环语句时，算法的时间复杂度是由于嵌套层数最多的循环语句中最内成循环的频度 f（n）决定的。因此该算法段的时间复杂度为 T（n）=O（n^3）

Case3:

x=1;
for(i=1;i<=n;i++){
      for(j=1;j<=n;j++){
           for(k=1;k<=n;k++){
               x++;
           }
        }
    }
复制代码

分析：

首先该算法的频度最大的语句是 x++;频度为3，从内层循环向外层循环分析该语句执行的次数为：[n(n+1)(2n+1)/6+n(n+1)/2]/2 因此结合时间复杂度的规律 T（n）=O（n^3/6+低次项）=O（n^3）

即时间复杂度为T（n）=O（n^3）

Case4：

i=1;
while(i<=n){
    i=i*2;
}
复制代码

分析：

设定以上while循环为k次，那么2^k 则2^k=n ,所以循环的次数为 log2n，因此算法的时间复杂度为O（log2n）

Case5（算法时间复杂度有时还会与输入实例的初始状态有关。）：

在数值A【0，n-1】中查找给定值k的算法如下：
i=n-1;
while(i>=0 and A [i] <>k ){
    i=i-1;
    return i;
}
复制代码

分析：

该算法不仅仅与问题规模有关，还与输入的实例A的各元素取指以及k的取值有关

1. 若A中没有与k相等的元素，这语句while的频度f（n）=n；这是最坏的情况
2. 若A中的第一个元素等于k，这语句while的频度f（n）为常数1，这是最好的情况

在求平均情况时，一般地假设查找不同元素的概率P是相同的，则算法的平均复杂度为1/n（1+2+3+4+....+n）=n+1/n=O(n)

若查找不同元素的概率p不相同时，其算法复杂度就只能做近似分析或在构造更好的算法或存储结构后，做比较准确的分析。