时间复杂度和空间代价

一、算法定义
算法设计的目标：时间和空间、还有健壮和可读等。

二、算法分析
1、时间复杂度
算法的时间代价是指算法执行时所花费的CPU时间量，通常用时间复杂度来度量：
举例理解：
①一条简单的语句时间复杂度为 O(1)

int   count  =  0;

②执行n次的循环语句，时间复杂度为 O(n)

int n = 8,count = 8 ;
for (int i = 1;i <= n ; i++){
      count ++;
}

③时间复杂度为O(log₂n)的循环语句如下：

int  n = 8,count = 0;
for (int i = 1;i<n ; i * = 2){
      count ++;
}
//其中，i 的取值为 1、2、4、8，循环执行1+log<sub>2</sub>n次，故循环语句的时间复杂度为：O(log<sub>2</sub>n)

④时间复杂度为O(n²)的二重循环如下

int n = 8 ,count = 0;
for (int i = 1 ; i<=n ; j++){
      for(int j= 1;j<=i ; j++){
            count ++;
      }
}

⑤O(n×log₂n)的二重循环

int n = 8 ,count = 0;
for ( int i= 1 ;i<=n ;i* = 2){
      for (int i = 1 ;j<=n ; j++){
            count ++;
     }
}

⑥O(n) ：二重循环

int n = 8, count =0;
for ( int =1;i<=n ; i* = 2){
       for(int  i = 1 ;i<= i ;j ++){
              count ++;
      }
}

2、空间复杂度
算法的空间代价是指算法执行时所占用的存储空间量。
执行一个算法所需要的存储空间包括三部分：
输入数据占用的存储空间、程序指令占用的存储空间、辅助变量占用的存储空间。
举例说明：
交换两个变量i,j算法，除了程序指令和i,j本身占用的存储空间以外，为了实现交换操作，还必须声明一个temp 变量， 这个temp 变量所占用的1个存储单元就是交换变量算法的空间复杂度O(1) 。